BOJ 12771 - Oil

BOJ 12771 - Oil

항상 정답이 되는 직선은 어떤 두 직선의 양 끝점을 잇는다고 가정하자.

naive하게는 $O(n^3)$이 걸린다. 직선들의 양 끝점 두 개를 잡고 다른 모든 직선들에 대해 겹치는지 검사를 할 수 있기 때문이다.

이걸 $O(n^2 \log n)$ 으로 줄이면 이 문제를 풀 수 있다.

모든 $2n$ 개의 점에 대해 돌면서 다른 모든 점들을 각도순으로 정렬하고 스위핑을 한다고 하면,

$O(2n \cdot \log (2n) \cdot 2n)$ 이므로 풀 수 있을 것 같다.

이 방법으로 시도해보겠다.

1년만의 재도전

$11$퍼 까지 가다 틀려버렸다.

구현이 잘못된것 같다.

Graham Scan처럼 가장 왼쪽 점을 기준으로 잡고 CCW에 따라 정렬하는 것 이 아닌 점들 중 임의의 점을 기준으로 $360 \degree$ 로 정렬을 해야하기 때문에 까다롭다.

요지는 어떤 구간이 $[x_1,x_2]$ 라면 항상 $x_1$에 더해줘야하고 $x_2$에 빼줘야하지 않고 도는 방향에 따라 반대가 될 수도 있다는 것이다.

또한 360도로 정렬하는 글도 참고했다.

두 구간으로 나눈다음에 정렬하면 된다고 한다.

나는 오른쪽 반직선을 시작으로 시계방향으로 $360 \degree$를 돌릴 것이므로 $1,2$ 사분면과 $3,4$ 사분면을 각각 정렬해줄 것이다.

그리고 이 문제에서도 항상 직선은 지표면과 닿아야 하므로 동일한 $y$ 에 대해서 직선을 그을 수 없기 때문에 그것이 더 알맞다.

추가적으로 구현에서 잘못 생각한 것은 360도 스위핑을 해줄 필요가 없었다는 것이다.

왜냐면 $y<0$ 이라면 기준점 대칭을 통해 $y>0$ 으로 만들어줘서 $180 \degree$에 대해서만 스위핑해줄 수 있다.

이렇게 구현하고 제출하니 $46$퍼에서 WA가 나왔다.

뭐가문젠가…

Assert 문을 찍어보다가 놀라운 사실을 발견했는데 $x_1 > x_2$ 인 경우가 있다는 것이다.

ㅅㅂ 출제자 인성 어디?