문제 링크
- http://icpc.me/12771
문제 출처
- 2016 ICPC World Final G번
사용 알고리즘
- 각도 정렬
- 스위핑
시간복잡도
- $O(N^2 log N)$
풀이
지표면에서부터 직선을 긋는 것이 아닌, 땅속 어느 점에서 시작해 기울기가 0이 아닌 직선을 긋는다고 생각해봅시다.
(x1, x2, y)선분 위의 점에서 시작해 직선을 그을 때는 (x1, y), (x2, y)처럼 선분의 끝부분에서 직선을 긋는 것이 이득이라는 것을 관찰할 수 있습니다.
이 사실을 통해 직선의 시작점으로 2N개만 보면 된다는 사실을 알 수 있습니다.(선분 N개의 양 끝점)
각 시작점에서의 최댓값을 찾는 방법을 생각해봅시다.
직선을 그을 것이기 때문에, 시작점보다 아래쪽에 있는 점은 시작점을 기준으로 점대칭 이동을 해도 상관 없습니다. 또한 기울기가 0이 아닌 직선을 그을 것이기 때문에 시작점과 y좌표가 같은 선분은 볼 필요가 없습니다.
모든 점들을 시작점보다 위에 오도록 세팅을 하고 문제를 풀어봅시다.
모든 점들을 시작점(S)보다 위로 올렸으니, 대충 위 그림과 같은 상황일 것입니다. 이제 시작점을 기준으로 직선을 여러 개 그어서 그중 최댓값을 찾을 것입니다.
정확히는, 직접 긋는 것이 아니라 스위핑 하면서 최댓값만 구할 것입니다.
스위핑을 하기 위해 위 그림처럼 각도 순으로 정렬을 해줍시다. 각도 순으로 점들의 번호를 붙여주면 각 선분을 (1, 2), (3, 5), (4, 7), (6, 8)로 표현할 수 있습니다.
여기에서 알 수 있는 사실은, S와 1번 점을 잇는 각도와 2번 점을 잇는 각도 사이에서 직선을 그으면 선분(1, 2)를 지나는 직선이 됩니다. 마찬가지로 4번 점을 잇는 각도와 7번 점을 잇는 각도 사이에서 직선을 그으면 선분 (4, 7)을 지나는 직선이 됩니다.
그러므로 점들을 각도 순으로 보면서 각 선분마다 점을 처음 만나면 현재 값에 선분의 길이를 더해주고, 두 번째로 만다면 선분의 길이를 빼줄 수 있습니다. 당연히 최댓값은 점들을 하나씩 볼 때마다 갱신하면서 구할 수 있습니다.
이렇게 하면 잘 해결될 것 같았지만, 아래 그림과 같은 반례가 있습니다.
이렇게 여러 개의 점이 같은 각도에 존재하는 경우에는 더하는 것을 모두 해준 다음에 최댓값을 갱신하고, 빼주는 것은 나중에 처리해야 합니다. 저는 각 점을 만날 때마다 더해야 하는 값들을 저장한 뒤, 각도가 같은 경우에는 더해야 하는 값이 큰 점을 먼저 보도록 정렬하는 방식을 사용했습니다.
발상/구현 모두 크게 어려운 문제는 아니지만 구현 실수를 할만한 부분이 많은 것 같습니다.