n개의 흑점과 n개의 백점이 2차원 평면상에 주어진다.
단, 어느 3개의 점도, 흑점이나 백점이나 막론하고, 일직선상에 있지 않다.
이때 흑점과 백점을 하나의 쌍으로 선분을 그리되 어떤 선분도 교차하지 않도록 n개의 흑-백 점 쌍을 찾고자 한다.
아래의 그림에서 왼쪽은 잘 짝이 맺어 졌으나, 오른쪽은 선분이 교차하여 잘 못 짝이 맺어진 경우이다.
이 문제를 해결하기 위한 분할정복 알고리즘을 제시하시오.
(그림은 첨부파일에 있습니다)
이런 문제는 어떻게 풀어야 하나요?
도와주세요~~~~ 도와주세요~~~
감도 안잡혀요~~~ ㅠ ㅠ
