| [ QuizWit ] in KIDS 글 쓴 이(By): valken (:이쁜왕자:) 날 짜 (Date): 2003년 7월 3일 목요일 오전 11시 27분 01초 제 목(Title): 폴리곤의 충돌 체크?? N 개 와 M 개의 점으로 주어지는 두개의 폴리곤 P1, P2가 있습니다. 이 두개의 폴리곤의 '충돌'하는지 체크하고 싶습니다. 계산의 편의를 위해서 한점이라도 만나면 충돌로 간주합니다. for ( P1 의 모든 선분) for ( P2 의 모든 선분) 선분의 교차 체크 if ( 1개라도 선분이 교차하면) 폴리곤 충돌!! (끝) P1 의 임의의 한점이 P2 의 내부에 있는지 체크 if ( 내부라면) 폴리곤 충돌 (P1 이 P2 에 포함됨) (끝) P2 의 임의의 한점이 P1 의 내부에 있는지 체크 if ( 내부라면) 폴리곤 충돌 (P2 가 P1 에 포함됨) (끝) 모두 아니라면 충돌 아님. .. 이 알고리즘의 time complexity 는 과연.. -_-! 좀 더 효율적인 알고리즘은 없을런지. "웬 초콜릿? 제가 원했던 건 뻥튀기 쬐끔과 의류예요." "얘야, 왜 또 불평?" -> 자음 19개와 모음 21개를 모두 사용하는 pangram - 이쁜왕자 - - Valken the SEXy THief~~ ^_* - |