| [ QuizWit ] in KIDS 글 쓴 이(By): Convex (4ever 0~) 날 짜 (Date): 1998년 6월 8일 월요일 오후 05시 22분 09초 제 목(Title): 두 뽈록다각형의 common tangent 뽈록 다각형이기 때문에 한점에서 다른 다각형의 점까지 선분을 그으면 그 선분의 길이가 줄어들거나 늘어나거나 하겠죠. 그런데 딱 한번만 그 방향이 바뀌게 되어있습니다. 그 성질을 이용하면 m * n 번 할 필요없지요. 한번 지나간 것은 다시 돌아오지 못할 다리를 건넌 것이기에 O(n + m) 이면 충분합니다. (최소거리 구하는 문제에서) *********** 그리고 두 뽈록다각형의 common tangent 구하는 문제에서.. 최대 4개 나오지만.. 그냥 lower tangent 구하는 알고리즘만 베껴볼께요. a <-- rightmost point of A b <-- leftmost point of B while T = ab not lower thngent to both A and B do while T not lower tangent to A do a <-- a - 1 while T not lower tangent to B do b <-- b + 1 (반시계 방향으로 미리 소팅 되어있다 가정) tangent 구하는 문제도 한번 지나간 것은 다시 볼 필요 없습니다. 가령 A의 0 에서 B의 11 12가 보인다면..(보인다(visible)는 말은 그 점끼리 잇는 선분이 다른 어떤 것과도 교차하지 않을 경우. 보이던 것이 안보이는 경우는 선분이 이루는 각도가 증가하다가 갑자기 감소한다거나..(A에서 B를 봤을 때) 그 각도가 감소하다가 갑자기 증가한다던가..(B에서 A를 봤을 때) constant time에 알 수 있습니다) (0 11)을 기억하고 있다가.. B의 11에서 보이는 A의 점을 차례로 찾아나갑니다. 예를 들어 1 2 3 4 까지 visible 했다면 4에서 다시 B의 점들을 찾는데 11부터 시작하면 되지요. 그러면 10 9 8 7ㄲK지 visible이라고 가정하면.. 다시 B의 7 지점에서 그치게 되는 경우. 뽈록 다각형이기 때문에 각 점을 돌때 이루는 각도의 변화를 비교해보고 선분의 각도를 비교해보면 tangent line인지 아닌지 알 수 있습니다. (즉 constant time으로 어떤 선분이 common tangent 인지 아닌지 알 수 있음) 이것 역시 O(n + m)이면 충분하지요. ****** 그리고 스칼라님의 의견에 대해서. 좀 제가 헷갈리게 썼나보네요. 우선 다각형끼리 겹치는 것을 1번이라고 하고, 다각형의 경계선이 겹치는 것을 2번 경우라고 하죠. 1번 경우라면 반드시 한쪽의 다각형 vertex가 다른쪽 다각형 내부에 있는가? => No. (박종대님의 counter example. 경계끼리 intersect하면서도 다른 다각형 내부에 vertex가 들어가는 일이 없는 경우. 또 다른 counter example이... 다비드의 별(이스라엘 별모양) 모양도 그런 경우죠. 공통부분 (n+m)- gon 생기는 특별한 경우가 바로 이런경웁니다.) 그렇다면 다각형이 겹치는 경우라면(1번) 반드시 다각형 경계끼리 intersect하게 되는가(2번) ? =>No. (완전히 포함되어 경계가 겹치지 않는 경우. 하지만 다각형끼리 겹침. 즉 edge의 intersect 따지는걸로도 충분하지 않음) ****** 여러가지 프로퍼티에 대해서는 박종대님이 위에 잘 정리해 두신듯 합니다. --,--`-<@ 매일 그대와 아침햇살 받으며 매일 그대와 눈을 뜨고파.. 잠이 들고파.. Till the rivers flow up stream | Love is real \|||/ @@@ Till lovers cease to dream | Love is touch @|~j~|@ @^j^@ Till then, I'm yours, be mine | Love is free | ~ | @@ ~ @@ |