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$ 인 경우가 있다는 것이다.
ㅅㅂ 출제자 인성 어디?
Comments