| [ QuizWit ] in KIDS 글 쓴 이(By): scalar (스칼라(數)) 날 짜 (Date): 1998년 6월 8일 월요일 오전 11시 56분 31초 제 목(Title): Re: algorithm 1 re를 달아 죄송합니다만, 앞서의 문제에서 볼록 다각형이라고 했던 걸로 기억합니다. 따라서, 앞서 박종대님의 예는 불가능할 것같구요. 4ever 0~님이 말씀하신 완전 포함되는 경우는 당연히 겹치는 경우로 보여지는데요. -------------------- 두개의 볼록 다각형이 겹치는지 안 겹치는지는 가장 단순하게 양쪽의 정점들을 단순 비교함으로써 해결할 수있습니다. (볼록 다각형이기에) 조금 머리를 쓴다면 4개의 tangent line을 구해 그 관계를 통해서도 판별해낼 수 있지요. tangent line을 구하는데 소요되는 시간은 O(logn)입니다. 물론 볼록 다각형이 angle에 의해 정렬된 상태여야 하지요. 그리고, 알고리즘에서 다각형이라고 한다면 최소한 어떤 기준에 의해 정렬된 상태여야 합니다.(x 축이든 angle이든) 참, tangent line을 구한다는 것은 한쪽 볼록 다각형의 어떤 점에서 구한다는 의미로 모든 점에 대해 구하려면 O(nlogn) 시간이 소요됩니다. (양쪽 다각형의 정점이 모두 O(n)이라는 전제하에 말하고 있습니다.) 그래서 O(nlogn)이라고 생각하는데요. 이게 최적인지는 모르겠습니다. >>>>>>>>>>>> rk.ca.gnagos.2balgla@ralacs >>>>>>>>>>>>>>>>>>>>>>> 내가 사랑하는 모든 이에게 항상 기쁨과 축복이 있기를 그리고, 나를 사랑하는 모든 이에게도 ......... <<<<<<<<<<<<<<<<<<<<<<<<<<<< scalar@alglab2.sogang.ac.kr <<<<<<< |