| [ QuizWit ] in KIDS 글 쓴 이(By): valken (:이쁜왕자:) 날 짜 (Date): 2003년 7월 3일 목요일 오전 11시 16분 33초 제 목(Title): 폴리곤 안에 점이 포함되어있는지 체크?? 선분의 교차에 이어서, n 개의 점으로 주어지는 폴리곤이 있습니다. 이 폴리곤 안에 어떤 점이 들어 있는지 아닌지를 확인하고 싶습니다. 폴리곤이 컨벡스라면 아주 간단하게 확인할수 있죠. 하지만 폴리곤은 컨벡스 뿐만 아니라 오목할수도 있고, 심지어, *-----* \ / \ / X / \ / \ *-----* 처럼 꼬여 있을수 있습니다. 더 극단적으로는 별모양 같은 경우도 있습니다. 이 경우 가운데 5각형은 '안'이 아니죠. 폴리곤을 여러개의 컨벡스의 조합으로 자르면 될듯 한데, 적당한 알고리즘이 있는지요. "웬 초콜릿? 제가 원했던 건 뻥튀기 쬐끔과 의류예요." "얘야, 왜 또 불평?" -> 자음 19개와 모음 21개를 모두 사용하는 pangram - 이쁜왕자 - - Valken the SEXy THief~~ ^_* - |