직사각형의 변 위에 여러 모양의 점들이 있고, 같은 모양의 점들은 정확히 두 개씩 있다.

단, 직사각형의 꼭지점에 놓인 점은 없다. 이제 같은 모양의 두 점들을 직선이나 곡선으로 연결하려고 한다.

연결된 선들은 반드시 직사각형의 내부만을 지나야 하며, 세 개 이상의 연결선들이 한 점에서 만나서는 안된다.

연결선과 연결선이 만나는 교차점의 개수를 가장 작게 하려고 할 때 최소 교차점의 개수를 구하는 프로그램을 작성하시오.

예를 들어, 점들이 아래 그림과 같이 주어졌다고 하자.

각 점의 위치는 두 개의 양의 정수로 표시된다.

첫째 숫자는 점이 위치한 변을 나타내는데, 1은 윗변, 2는 밑변, 3은 왼쪽 변, 4는 오른쪽 변을 의미한다.

둘째 숫자는 변 위에서의 위치를 나타낸다.

점이 윗변이나 밑변에 있는 경우는 왼쪽 꼭지점부터의 거리를 나타내고, 점이 왼쪽 변이나 오른쪽 변에 있는 경우는 위쪽 꼭지점부터의 거리를 나타낸다.

즉, 점 (4, 7)은 오른쪽 변에 있는 점으로 변의 위쪽 꼭지점으로부터 거리 7만큼 떨어져 있다.

이 그림에서, 두 점(3, 5)와 (4, 7)을 점선과 같이 연결하여, 세 개의 연결선들이 한 점에서 만나게 하면 안된다.

이 그림에서 최소 교차점의 개수는 4이다.

교차점개수 timer 1초 memory 64MB

교차점개수 1초 64MB