백준 2162 (C++) 선분 그룹

최초 업로드: 2025-07-31 11:11:48

최근 수정 시간: 2025-07-31 11:12:59

게시자: rlatjwls3333

카테고리: 백준

# [Platinum V] 선분 그룹

[문제 링크](https://www.acmicpc.net/problem/2162)

## 문제 설명

N개의 선분들이 2차원 평면상에 주어져 있다. 선분은 양 끝점의 x, y 좌표로 표현이 된다.

두 선분이 서로 만나는 경우에, 두 선분은 같은 그룹에 속한다고 정의하며, 그룹의 크기는 그 그룹에 속한 선분의 개수로 정의한다. 두 선분이 만난다는 것은 선분의 끝점을 스치듯이 만나는 경우도 포함하는 것으로 한다.

N개의 선분들이 주어졌을 때, 이 선분들은 총 몇 개의 그룹으로 되어 있을까? 또, 가장 크기가 큰 그룹에 속한 선분의 개수는 몇 개일까? 이 두 가지를 구하는 프로그램을 작성해 보자.

## 입력

첫째 줄에 N(1 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N+1번째 줄에는 양 끝점의 좌표가 x1, y1, x2, y2의 순서로 주어진다. 각 좌표의 절댓값은 5,000을 넘지 않으며, 입력되는 좌표 사이에는 빈칸이 하나 있다.

## 출력

첫째 줄에 그룹의 수를, 둘째 줄에 가장 크기가 큰 그룹에 속한 선분의 개수를 출력한다.

## 풀이
#### 각 선분끼리 교점이 있는지 ccw로 확인하고 분리집합으로 합쳐서 구하면 됩니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

struct line {
    int x1, y1, x2, y2;
};

int ccw(line a) {
 int ret = a.x1*a.y2 - a.x2*a.y1;
 if(ret>0) return 1;
 if(ret<0) return -1;
 return 0;
}

bool isIntersect(line a, line b) {
    int aToB1 = ccw({a.x2-a.x1, a.y2-a.y1, b.x1-a.x2, b.y1-a.y2});
    int aToB2 = ccw({a.x2-a.x1, a.y2-a.y1, b.x2-a.x2, b.y2-a.y2});
    int bToA1 = ccw({b.x2-b.x1, b.y2-b.y1, a.x1-b.x2, a.y1-b.y2});
    int bToA2 = ccw({b.x2-b.x1, b.y2-b.y1, a.x2-b.x2, a.y2-b.y2});

if(aToB1 * aToB2==0 && bToA1 * bToA2==0) {
 return (min(a.x1, a.x2)<=b.x1 && b.x1<=max(a.x1, a.x2) || min(a.x1, a.x2)<=b.x2 && b.x2<=max(a.x1, a.x2) || min(b.x1, b.x2)<=a.x1 && a.x1<=max(b.x1, b.x2) || min(b.x1, b.x2)<=a.x2 && a.x2<=max(b.x1, b.x2))
 && (min(a.y1, a.y2)<=b.y1 && b.y1<=max(a.y1, a.y2) || min(a.y1, a.y2)<=b.y2 && b.y2<=max(a.y1, a.y2) || min(b.y1, b.y2)<=a.y1 && a.y1<=max(b.y1, b.y2) || min(b.y1, b.y2)<=a.y2 && a.y2<=max(b.y1, b.y2));
 }
 return aToB1 * aToB2 <= 0 && bToA1 * bToA2 <= 0;
}

const int MAX = 3000;

int parent[MAX], _size[MAX];

int _find(int x) {
    if(parent[x]==x) return x;
    return parent[x] = _find(parent[x]);
}

void _union(int x, int y) {
 x = _find(x);
 y = _find(y);
 if(x<y) {
 parent[y]=x;
 _size[x] += _size[y];
 } else if(x>y) {
 parent[x]=y;
 _size[y] += _size[x];
 }
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n; cin >> n;
 vector<line> lines(n);
 for(int i=0;i<n;i++) {
 parent[i]=i;
 _size[i]=1;
 cin >> lines[i].x1 >> lines[i].y1 >> lines[i].x2 >> lines[i].y2;
 for(int j=0;j<i;j++) {
 if(isIntersect(lines[i], lines[j])) {
 _union(i, j);
 }
 }
 }

int cnt=0, maxSize=1;
 for(int i=0;i<n;i++) {
 if(i==parent[i]) cnt++;
 maxSize = max(maxSize, _size[i]);
 }
 cout << cnt << '\n' << maxSize;
}
```