취미로PS하는사람

https://www.acmicpc.net/problem/3121 그 테크닉을 배웠다. (2022.1.5 추가: rotating sweep line 이라고 부르는 것 같다.) $N$개의 점이 있을 때, 특정 기울기의 법선 벡터를 가지는 직선에 점들을 정사영하여 그 순서를 알고 싶다. 만약 Naive하게 구현한다면 각도는 최대 $O(N^2)$개, 점들의 정렬에 대략 $O(Nlog{N})$이 소요될 것이므로 시간이 너무 오래 걸린다. 하지만 잘 생각해보면 정렬된 상태는 법선벡터와 어떤 두 점을 잇는 직선의 기울기가 동일해질 때 그 두 점의 위치만 인접한 상태에서 바뀌기 때문에, 점 쌍들을 기울기로 정렬하여 순서대로 두 점의 위치만 바꾸어주면 모든 $N^2$개의 각도에서 정사영한 순서를 알 수 있다. 각도 정..