2162_선분그룹

https://www.acmicpc.net/problem/2162 2162번: 선분 그룹 첫째 줄에 N(1 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N+1번째 줄에는 양 끝점의 좌표가 x1, y1, x2, y2의 순서로 주어진다. 각 좌표의 절댓값은 5,000을 넘지 않으며, 입력되는 좌표 사이에는 빈칸이 하 www.acmicpc.net CCW 알고리즘과 Union find 알고리즘을 같이 사용하면 풀수 있을꺼 같아서 적용하여 풀었다. 우선 CCW알고리즘을 이용하여 두 선분이교차하는지 하지 않는지 판단하는 함수를 하나 만들고, union find 알고리즘을 활용하여 두 선분이 교차하였다면 한 그룹으로 묶어주는 과정을 진행한다. 이때 주의할 점은 parents 배열을 마지막에 꼭 압축해줘야 한다. ..