BOJ 12771 Oil (ACM-ICPC 2016 WF)

https://www.acmicpc.net/problem/12771

12771번: Oil

직선을 하나 그어, x 축에 수평한 선분을 최대한 많이 지나가게 만드는 문제이다. (지나가는 선분의 합을 최대화)

직선이 선분의 끝에 닿아도 지나간 것으로 간주한다. 최적의 방법이 존재할 때, 그 직선을 직선이 지나가는 어느 한 선분의 끝자락에 닿을 때까지 당겨도 최적임에는 변함이 없다. 따라서 어떤 한 선분의 끝을 지나는 최적해가 존재한다.

직선이 선분 a의 어느 한 끝 점 p를 지난다고 하고,그 직선이 지날 수 있는 최대 선분을 구하는 방법을 생각해 보자.
직선을 점 p에 고정하고, 직선을 180도 회전하면서 직선이 다른 선분에 끝에 닿기 시작하면 +1, 선분의 반대편 끝에 닿아 떨어지면 -1을 하여, 직선이 지나는 선분의 수를 카운트할 수 있다.

따라서 어떤 점 p에 대해, 모든 선분의 양 끝 점의 p에 대한 각도를 기준으로 정렬을 한 뒤, 직선을 한 바퀴 돌려 직선이 지나는 최대 선분의 수를 구할 수 있다. (O(log n))

모든 선분의 양 끝점에 대해, 위 과정을 반복하여 직선이 지나는 최대 선분의 수를 구할 수 있다.

이 문제에서는 선분의 수가 아니라, 선분의 길이를 구하는 것이므로, +1/-1 대신 선분의 길이를 더하고 빼면 된다.

Note:

• 기준이 되는 점 p보다 y축 기준으로 아래에 위치한 선분을 p에대해 점대칭 이동할 수 있다. 이동 변환 결과 모든 선분은 p보다 위에 위치하게 되므로 조건을 간략화할 수 있다.
• 선분들을 점 p에 대해서 정렬을 할 때, 각도가 같은 선분이 여러개가 있는 경우, 선분에 진입하는 경우를 항상 선분에서 빠져나오는 경우보다 우선시해야 한다. 우선 진입과 이탈을 기준으로 정렬을 한 뒤, 각도를 기준으로 stable 정렬을 하면 된다.