이 글에서는 평면 위에 놓인 가로(수평) 선분과 세로(수직) 선분들이 서로 교차하며 생기는 교점들을 연결할 때, 만들 수 있는 삼각형의 총 개수를 구하는 C++ 프로그램을 소개합니다.
예를 들어 아래 그림과 같은 선분들이 주어졌다고 가정해 보겠습니다. 이 선분들은 총 3개의 교점을 형성하며, 3개의 점으로 만들 수 있는 삼각형의 개수는 조합 공식에 따라 3C3 = 1가지입니다.
| ---|--------|-- | | | --|---| | |
접근 방식: 스윕 라인(Sweep Line) 알고리즘
이 문제는 스윕 라인 알고리즘과 펜윅 트리(Binary Indexed Tree, BIT)를 함께 활용하면 효율적으로 해결할 수 있습니다. 먼저 모든 선분의 좌표 값을 이벤트 형태로 저장한 뒤, 한 선분의 내부 구간이 다른 선분과 교차하는지 검사합니다. 이 과정을 통해 주어진 선분들 사이의 모든 교점을 구할 수 있고, 마지막에는 조합 공식을 적용해 가능한 삼각형의 개수를 손쉽게 계산할 수 있습니다.
동작 흐름을 정리하면 다음과 같습니다.
① 수평 선분은 왼쪽 끝점(시작 이벤트, 타입 1)과 오른쪽 끝점(종료 이벤트, 타입 2)으로 변환하고, 수직 선분은 위·아래 끝점 두 곳(타입 3)으로 변환합니다. ② 이벤트들을 x좌표 기준으로 정렬합니다. ③ 스윕 라인이 지나갈 때 수평 선분의 시작 지점에서는 BIT에 y좌표를 추가하고(+1), 종료 지점에서는 제거합니다(−1). ④ 수직 선분을 만나면 해당 구간 [bottom, top] 사이에 걸려 있는 수평 선분의 개수를 BIT 질의(query)로 구해 교점 수에 누적합니다.
이렇게 구한 교점의 개수를 k라고 할 때, 만들 수 있는 삼각형의 개수는 k × (k − 1) × (k − 2) ÷ 6, 즉 kC3입니다. 교점이 3개보다 적으면 만들 수 있는 삼각형은 없으므로 0을 반환합니다.
구현 예시
#include<bits/stdc++.h>
#define maxy 1000005
#define maxn 10005
using namespace std;
//to store intersection points
struct i_point {
int x, y;
i_point(int a, int b) {
x = a, y = b;
}
};
int bit[maxy];
vector < pair <i_point, int> > events;
//to sort the given points
bool com_points(pair<i_point, int> &a, pair<i_point, int> &b) {
if ( a.first.x != b.first.x )
return a.first.x < b.first.x;
else {
if (a.second == 3 && b.second == 3) {
return true;
}
else if (a.second == 1 && b.second == 3) {
return true;
}
else if (a.second == 3 && b.second == 1) {
return false;
}
else if (a.second == 2 && b.second == 3) {
return false;
}
return true;
}
}
void topdate_line(int index, int value) {
while (index < maxn) {
bit[index] += value;
index += index & (-index);
}
}
int query(int index) {
int res = 0;
while (index > 0) {
res += bit[index];
index -= index & (-index);
}
return res;
}
//to insert a line segment
void insertLine(i_point a, i_point b) {
//in case of horizontal line
if (a.y == b.y) {
int begin = min(a.x, b.x);
int end = max(a.x, b.x);
events.push_back(make_pair(i_point(begin, a.y), 1));
events.push_back(make_pair(i_point(end, a.y), 2));
}
//in case of vertical line
else {
int top = max(b.y, a.y);
int bottom = min(b.y, a.y);
events.push_back(make_pair(i_point(a.x, top), 3));
events.push_back(make_pair(i_point(a.x, bottom), 3));
}
}
//to calculate number of intersection points
int calc_i_points() {
int i_points = 0;
for (int i = 0 ; i < events.size() ; i++) {
if (events[i].second == 1) {
topdate_line(events[i].first.y, 1);
}
else if (events[i].second == 2) {
topdate_line(events[i].first.y, -1);
}
else {
int bottom = events[i++].first.y;
int top = events[i].first.y;
i_points += query(top) - query(bottom);
}
}
return i_points;
}
int calc_triangles() {
int points = calc_i_points();
if ( points >= 3 )
return ( points * (points - 1) * (points - 2) ) / 6;
else
return 0;
}
int main() {
insertLine(i_point(3, 2), i_point(3, 13));
insertLine(i_point(1, 5), i_point(3, 5));
insertLine(i_point(8, 2), i_point(8, 8));
insertLine(i_point(3, 4), i_point(6, 4));
insertLine(i_point(4, 3), i_point(4, 5));
sort(events.begin(), events.end(), com_points);
cout << "Possible number of triangles : " << calc_triangles() << endl;
return 0;
}코드 구성 요소 살펴보기
- i_point 구조체 : 교점의 x, y 좌표를 저장합니다.
- insertLine() : 입력받은 선분을 이벤트 목록에 추가합니다. 수평 선분은 시작(1)·종료(2) 이벤트로, 수직 선분은 양 끝점(3)으로 등록합니다.
- com_points() : 이벤트를 x좌표 기준으로 정렬하되, 같은 x좌표에서는 수평 시작 → 수직 → 수평 종료 순서로 처리되도록 비교 규칙을 정의합니다.
- topdate_line() / query() : 펜윅 트리(BIT)의 값 갱신과 구간 합 질의를 담당합니다.
- calc_i_points() : 정렬된 이벤트를 순회하며 수직 선분 구간과 교차하는 수평 선분의 개수를 누적해 총 교점 수를 계산합니다.
- calc_triangles() : 구한 교점 수 k에 대해 k × (k−1) × (k−2) ÷ 6 공식을 적용해 삼각형의 개수를 반환합니다.
실행 결과
Possible number of triangles : 1
위 예제에서는 5개의 선분이 서로 교차하여 총 3개의 교점을 만들며, 따라서 만들 수 있는 삼각형은 정확히 1개임을 확인할 수 있습니다. 시간 복잡도는 이벤트 정렬에 O((N+M)log(N+M)), BIT 연산에 로그 시간이 소요되어 전체적으로 매우 효율적으로 동작합니다.