문제 링크
- http://icpc.me/5255
문제 출처
- 2011 BalkanOI Day1 1번
사용 알고리즘
- Half Plane Intersection
- Rotating Calipers
시간복잡도
- $O(N log N log X)$
풀이
반지름이 $r$인 두 원을 넣을 수 있는지 판단할 수 있다면, 파라메트릭 서치를 이용해 답을 구할 수 있습니다.
볼록 다각형에서 각 변을 $r$만큼 안쪽으로 밀어넣은 새로운 볼록 다각형을 생각해봅시다.
$r$만큼 안쪽으로 들어간 볼록 다각형의 변에 원의 중심을 배치하고, 두 원이 겹치지 않도록 반지름 $r$짜리인 원을 넣을 수 있는지 판별하면 됩니다.
왼쪽 그림처럼 두 원을 겹치지 않게 놓을 수 있다면 반지름 $r$짜리인 원을 넣을 수 있는 것이고, 오른쪽 그림과 같은 경우에는 넣지 못합니다.
두 원이 겹치지 않는다는 것은 다각형의 변 위에 점 2개를 적당히 잡아 거리가 $2r$ 이상이 될 수 있다는 것이고, 이는 다각형의 지름이 $2r$ 이상인 것과 동치입니다.
그러므로 우리가 각 변을 $r$만큼 안쪽으로 밀어넣은 볼록 다각형을 잘 만들었다면 rotating calipers로 다각형의 지름을 구할 수 있습니다.
각 변을 $r$만큼 안쪽으로 밀어넣은 볼록다각형은 반평면 교집합(Half Plane Intersection)을 이용해 $O(N log N)$만에 구할 수 있습니다.
파라메트릭 서치를 포함해 $O(N log N log X)$ 시간에 문제를 해결할 수 있습니다.