전제 조건: 조금 주어진 'n'개의 선분은 각각 수평이거나 수직입니다. 선분의 교차점을 연결하여 형성할 수 있는 삼각형(면적이 0인 삼각형 포함)의 최대 수를 구하십시오. 두 개의 수평선 세그먼트가 겹치지 않으며 두 개의 수직선 세그먼트도 겹치지 않습니다. 선은 두 개의 점을 사용하여 표현됩니다(첫 번째 두 개의 정수는 각각 첫 번째 점의 x 및 y 좌표이고 나머지 두 개는 두 번째 점의 x 및 y 좌표임) 예:
| ---|-------|-- | | ----- | --|--|- | | | | For the above line segments there are four points of intersection between vertical and horizontal lines every three out of which form a triangle so there can be 4C3 triangles.
아이디어는 다음을 기반으로합니다. 스윕 라인 알고리즘 . 단계별로 솔루션 구축:
- 해당 이벤트(아래 설명)가 있는 모든 선분의 두 점을 벡터에 저장하고 모든 점을 x 좌표의 내림차순으로 정렬합니다.
- 이제 이 모든 지점을 가로지르는 수직선을 상상하고 현재 어느 지점에 있는지에 따라 3가지 이벤트를 설명하겠습니다.
- 에이 수직선
- 우리는 지역에 전화를 겁니다. '활동적인' 아니면 수평선 '활동적인' 첫 번째 이벤트는 있었지만 두 번째 이벤트는 발생하지 않았습니다. 모든 활성 라인의 'y' 좌표를 저장하는 BIT(Binary indexed tree)가 있습니다.
- 라인이 비활성화되면 BIT에서 'y'를 제거합니다.
- 세 번째 유형의 이벤트가 발생하면, 즉 수직선에 있을 때 'y' 좌표 범위의 트리를 쿼리하고 그 결과를 지금까지의 교차점 수에 추가합니다.
- 마지막으로 우리는 교차점의 수를 말하게 될 것입니다. 중 그러면 삼각형의 수(영 영역 포함)는 다음과 같습니다. 중기음3 .
~에 - 수평선 부분의 가장 왼쪽 지점밖으로 - 수평선 부분의 가장 오른쪽 지점메모: 주의 깊게 포인트를 정렬해야 합니다. cmp() 설명을 위해 구현 기능을 수행합니다.
CPP// A C++ implementation of the above idea #include
#define maxy 1000005 #define maxn 10005 using namespace std; // structure to store point struct point { int x y; point(int a int b) { x = a y = b; } }; // Note: Global arrays are initially zero // array to store BIT and vector to store // the points and their corresponding event number // in the second field of the pair int bit[maxy]; vector<pair<point int> > events; // compare function to sort in order of non-decreasing // x coordinate and if x coordinates are same then // order on the basis of events on the points bool cmp(pair<point int> &a pair<point int> &b) { if ( a.first.x != b.first.x ) return a.first.x < b.first.x; //if the x coordinates are same else { // both points are of the same vertical line if (a.second == 3 && b.second == 3) { return true; } // if an 'in' event occurs before 'vertical' // line event for the same x coordinate else if (a.second == 1 && b.second == 3) { return true; } // if a 'vertical' line comes before an 'in' // event for the same x coordinate swap them else if (a.second == 3 && b.second == 1) { return false; } // if an 'out' event occurs before a 'vertical' // line event for the same x coordinate swap. else if (a.second == 2 && b.second == 3) { return false; } //in all other situations return true; } } // update(y 1) inserts a horizontal line at y coordinate // in an active region while update(y -1) removes it void update(int idx int val) { while (idx < maxn) { bit[idx] += val; idx += idx & (-idx); } } // returns the number of lines in active region whose y // coordinate is between 1 and idx int query(int idx) { int res = 0; while (idx > 0) { res += bit[idx]; idx -= idx & (-idx); } return res; } // inserts a line segment void insertLine(point a point b) { // if it is a horizontal line if (a.y == b.y) { int beg = min(a.x b.x); int end = max(a.x b.x); // the second field in the pair is the event number events.push_back(make_pair(point(beg a.y) 1)); events.push_back(make_pair(point(end a.y) 2)); } //if it is a vertical line else { int up = max(b.y a.y); int low = min(b.y a.y); //the second field of the pair is the event number events.push_back(make_pair(point(a.x up) 3)); events.push_back(make_pair(point(a.x low) 3)); } } // returns the number of intersection points between all // the lines vertical and horizontal to be run after the // points have been sorted using the cmp() function int findIntersectionPoints() { int intersection_pts = 0; for (int i = 0 ; i < events.size() ; i++) { //if the current point is on an 'in' event if (events[i].second == 1) { //insert the 'y' coordinate in the active region update(events[i].first.y 1); } // if current point is on an 'out' event else if (events[i].second == 2) { // remove the 'y' coordinate from the active region update(events[i].first.y -1); } // if the current point is on a 'vertical' line else { // find the range to be queried int low = events[i++].first.y; int up = events[i].first.y; intersection_pts += query(up) - query(low); } } return intersection_pts; } // returns (intersection_pts)C3 int findNumberOfTriangles() { int pts = findIntersectionPoints(); if ( pts >= 3 ) return ( pts * (pts - 1) * (pts - 2) ) / 6; else return 0; } // driver code int main() { insertLine(point(2 1) point(2 9)); insertLine(point(1 7) point(6 7)); insertLine(point(5 2) point(5 8)); insertLine(point(3 4) point(6 4)); insertLine(point(4 3) point(4 5)); insertLine(point(7 6) point(9 6)); insertLine(point(8 2) point(8 5)); // sort the points based on x coordinate // and event they are on sort(events.begin() events.end() cmp); cout << "Number of triangles are: " << findNumberOfTriangles() << "n"; return 0; } 산출:
프롤로그가 뭐야?
Number of triangles are: 4
Time Complexity: O( n * log(n) + n * log(maximum_y) )
보조 공간: O(maxy) 여기서 maxy = 1000005