------ 한 현의 끝점을 a1, a2, 다른 현의 끝점을 b1, b2라고 할 때에 두 현이 원 안에서 만나려면 끝점이 a1, b1, a2, b2 식으로 교차해야 합니다. 원 안에서 만나지 않으면 a1, a2, b1, b2 식이 될테고요. 모든 현의 끝점을 정렬한 후에 위와 같이 겹치는 곳이 몇군데 있는지 검사하면 쉽게 n lg n 시간의 알고리즘을 구할 수 있습니다. ----- 그렇게 하면 모든 선들에 대해서 다른 선들이 겹치는 지를 검사해야 하니까 N^2 알고리즘이 되지 않나요? |