BOJ 18252 - 별이 빛나는 밤

문제 요약

 

두 점과 x축에 평행한 레일이 있다. 각 레일에서 한 점을 선택한 후 세 점으로 만들 수 있는 삼각형의 넓이의 최댓값의 최솟값을 구하여라.

 

풀이

별의 배치는 선분 \(AB\)에 가장 가깝게 하면 된다. 즉, 교차하면 교점 위에, 아니면 왼쪽 또는 오른쪽 끝에 두면 된다. 자세한 증명은 하지 않았기 때문에 생략하도록 하겠다.

최대 넓이를 가지는 삼각형은 convex hull 위에 있다. 따라서, 이 문제는 convex hull 위의 삼각형 중 최대 넓이를 가지는 것을 구하는 문제가 된다.

우선 한 점을 고정하고 다른 한 점을 반시계 방향으로 이동시킨다고 생각해보자. 그러면 이 선분과 가장 먼 점 2개는 선분의 이동 방향을 따라 캘리퍼스처럼 움직여줄 수 있다.

따라서 \(O(N^2)\)에 문제를 해결할 수 있다. 제곱인데 \(N = 10000\)에 1초라 시간 제한이 상당히 빡세다. 나는 남들보다 상수가 2배정도인 구현을 해서 몸을 비튼 후에야 맞을 수 있었다.