직사각형의 변 위에 여러 모양의 점들이 있고 같은 모양의 점들은 정확히 두 개씩 있다.단 직사각형의 꼭지점에 놓인 점은 없다.
이제 같은 모양의 두 점들을 직선이나 곡선으로 연결하려고 한다. 연결된 선들은 반드시 직사각형의 내부만을 지나야 하며 세 개 이상의 연결선들이 한 점에서 만나서는 안된다.
연결선과 연결선이 만나는 교차점의 개수를 가장 작게 하려고 할 때 최소 교차점의 개수를 구하는 프로그램을 작성하시오.
예를들어 점들이 아래 그림과 같이 주어졌다고 하자. 각 점의 위치는 두 개의 양의 정수로 표시된다.
즉, 점(4,7)은 오른쪽 변에 있는 점으로 변의 위쪽 점과 꼭지점으로부터 거리 7 만큼 떨어져 있다. 이 그림에서, 두 점(3,5)와(4,7)을 점선과 같이 연결하여 세 개의 연결선들이 한 점에서 만나게 하면 안된다. 이 그림에서 최소 교차점의 개수는 4 이다.
프로그램의 실행 시간은 10 초를 넘으면 안된다.
입력 10 3 5 4 7 1 7 2 8 2 4 2 7 2 6 4 4 1 5 3 3 출력 4 3
출처: koi 초등 기출