백준5255 2Circles

문제 링크

  • http://icpc.me/5255

문제 출처

  • 2011 Balkan OI 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)$ 시간에 문제를 해결할 수 있습니다.