shjgkwo   1년 전

지름이 D인, 다른말로 반지름이 D/2 인 원이 포함할수 있는 최대의 점개수를 구하는 문제 같네요 ㅠㅠ

맞나요..?

koosaga   1년 전

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

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


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


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

shjgkwo   1년 전

#2626 헬기 착륙장

문제의 응용이네요!


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

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

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

koosaga   1년 전

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

shjgkwo   1년 전

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

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

shjgkwo   1년 전

해냈어요 ㅠㅠ

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

축소가 아닌 확장이었네요

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

shjgkwo   1년 전

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

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

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

댓글을 작성하려면 로그인해야 합니다.