종이 위에 지름 D인 원을 그린 후, 지름 양 옆에 점 두개를 찍어보세요.

이제 두 점을 중심으로 하는 반지름 D의 원을 두개 그려보시면 아마 () 모양의 구역이 생길것입니다. 아까 그린 원보다 조금 더 크죠.

이제 () 구역에 속하고 아까 그린 원에 속하지 않는 점들은 모두 말씀하신 알고리즘의 반례입니다.

(문제에 대한 약간의 힌트이기도 합니다.)

#2626 헬기 착륙장

문제의 응용이네요!

음, 일단 지름이 D인 가장 많은 점을 포함하는 볼록껍질을 찾는 문제로 변형시킬수 있고..

그 볼록껍질을 포함하는 원을 구하는 문제로서, 어느 두 점을 잡고 그 두 점 사이 거리를 그 두점을 포함하는 볼록껍질의 지름이라고 가정한 뒤

그것을 그 볼록껍질을 포함하는 원의 반지름으로 잡고 다른 어느점에 닿을때까지 축소시키는 문제 맞나요?

지름이 D인 원하고 별로 상관없는 문제에요 ㅠㅠ

아뇨.. 원이 아니라 볼록껍질의 제일 긴 지름이 D요.. (정확히는 D보다 작거나 같은)

원은, 그 볼록껍질 찾는 수단으로 쓰구요..

해냈어요 ㅠㅠ

반례 덕분에 찾아낸 방법이긴 한데

축소가 아닌 확장이었네요

원을 점점 확장하는 방식으로 나가니 성공했어요 ㅠㅠㅠㅠ

O(n^4) 이라 간당간당 하긴 하지만, 어쨌든 해결되었네요 ㅠㅠ

원을 확장하는 과정에서 점을 추가할때마다 그 점이 다른 점과 통신이 되는지 확인하는 과정에서 O(n)의 반복문을 더 써서..

O(n^3) 이나, O(n^3 log n) 으로 푸는 방법이 있을것 같은데 도저히 모르겠네요 ㅠㅠ

와 1년전에 나는 병1신이었구나..

부끄럽다...

죄송합니다. @koosaga 님 ㅠㅠ