[BOJ 3679] 단순 다각형 "컷"
2022. 11. 17. 11:24ㆍPS/Problem Solving
https://www.acmicpc.net/problem/3679
3679번: 단순 다각형
첫째 줄에 테스트 케이스의 개수 c (1 ≤ c ≤ 200)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 테스트 케이스의 첫 번째 숫자는 점의 개수 n (3 ≤ n ≤ 2000) 이다. 다음 숫자는 점의 좌
www.acmicpc.net
CCW 정렬하면 될 것이라는 추측
실제로 된다.
1. 왼쪽 아래 점 (기준 8개 다 된다. 아래 오른쪽, 왼쪽 위 등) 기준으로 정렬
2. ccw가 같은 마지막 t개(t>=1) 점들의 경우 순서를 뒤집어주자. = 거리가 가까운 것부터 이어야 하므로
728x90
'PS > Problem Solving' 카테고리의 다른 글
| [BOJ 26035] “컷” $0101$ (1) | 2022.11.18 |
|---|---|
| [BOJ 25972] 도미노 무너트리기 "컷" (2) | 2022.11.17 |
| [BOJ 20295] 사탕배달 "컷" (2) | 2022.11.15 |
| [BOJ 3176] 도로 네트워크 "컷" (2) | 2022.11.15 |
| [BOJ 13334] 철로 "컷" (2) | 2022.11.15 |