| [ QuizWit ] in KIDS 글 쓴 이(By): iLUSiON (BBiZi Land) 날 짜 (Date): 1998년 6월 6일 토요일 오전 01시 15분 13초 제 목(Title): re: geomtery 5. 제가 위의 문제에서 간과한게 있는데 발켄씨가 지적한것같이 겹칠경우 정의에 의해서 거리를 0으로 둡니다. 만약 M,N을 각각의 폴리곤이라 칭할경우 겹치는지 안겹치는지 살피기 위해서는 max Px(M) < min Px(N) 인지 살펴야 합니다. 여기서 Px is a projection onto x-coordinates such that Px^2 = Px 마찬가지로 y좌표에 대해서도 살펴봐야 합니다. 결국은 m개의 점에서 막시멈과 미니멈을 찾고 n개의 점에서 막시멈과 미니멈을 찾는문제로 바뀝니다. 그런데 동시에 막시멈과 미니멈을 찾을경우는 러닝타임이 각각을 찾아서 2배해주는 것보다 줄어듭니다. 아마 대략 O(3n/2) 인데 토탈러닝타임은 그래서 O(3n/2 + 3m/2) 입니다. 위에서 geometry 5에서 알고리듬 이야기는 안하시고 그냥 러닝타임들만 적어주셨네요. 다 아는 알고리듬이라도 저는 처음보는문제니까 상세한설명좀 부탁합니다. ^^ * 나는 키즈를 파멸시키기 위해 멍멍이 아지와 함께 이땅에 태어났다. http://www.math.mcgill.ca/~chung |