| [ QuizWit ] in KIDS 글 쓴 이(By): cdpark (박종대) 날 짜 (Date): 1999년 10월 9일 토요일 오전 11시 02분 23초 제 목(Title): Re: from algorithm book 15.1-8 한 현의 끝점을 a1, a2, 다른 현의 끝점을 b1, b2라고 할 때에 두 현이 원 안에서 만나려면 끝점이 a1, b1, a2, b2 식으로 교차해야 합니다. 원 안에서 만나지 않으면 a1, a2, b1, b2 식이 될테고요. 모든 현의 끝점을 정렬한 후에 위와 같이 겹치는 곳이 몇군데 있는지 검사하면 쉽게 n lg n 시간의 알고리즘을 구할 수 있습니다. -- 박.. |