2018. 6. 21. 21:15, 알고리즘/BOJ
https://www.acmicpc.net/problem/2162
O(N^2)으로 겹치는 선분 쌍을 찾고, union-find로 합치면 됩니다. 선분이 겹치는지는 CCW로 판단할 수 있습니다. 일직선 상에 직선이 있는 경우를 잘 처리해주어야 합니다.
'알고리즘 > BOJ' 카테고리의 다른 글
| [BOJ] 2228번: 구간 나누기 (0) | 2018.06.22 |
|---|---|
| [BOJ] 1708번: 볼록 껍질 (0) | 2018.06.22 |
| [BOJ] 15684번: 사다리 조작 (2) | 2018.06.22 |
| [BOJ] 4225번: Trash Removal (0) | 2018.06.20 |
| [BOJ] 2213번: 트리의 독립집합 (0) | 2018.06.20 |
| [BOJ] 9250번: 문자열 집합 (0) | 2018.06.17 |
Comments