DAMPER's blog

https://www.acmicpc.net/problem/2162 2162번: 선분 그룹 첫째 줄에 N(1 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N+1번째 줄에는 양 끝점의 좌표가 x1, y1, x2, y2의 순서로 주어진다. 각 좌표의 절댓값은 5,000을 넘지 않으며, 입력되는 좌표 사이에는 빈칸이 하 www.acmicpc.net 문제 설명 선분의 양끝의 점 2개를 N번 입력받고 선분끼리 만나면 선분 그룹안에 속한다고 한다. 이 때, 선분 그룹의 갯수와 크기가 가장 큰 그룹의 선분 갯수를 출력하면 된다. 여기서 필요한 것은 두 선분이 만나는 것을 체크하는 것과 그룹을 만드는 것이다. 두 선분이 만나는지 아닌지를 판단하는 CCW와 그룹을 만드는 Disjoint-Set을 사용했다. 평소에 Di..