문제
직사각형의 변 위에 여러 모양의 점들이 있고, 같은 모양의 점들은 정확히 두 개씩 있다.
단, 직사각형의 꼭지점에 놓인 점은 없다. 이제 같은 모양의 두 점들을 직선이나 곡선으로 연결하려고 한다.
연결된 선들은 반드시 직사각형의 내부만을 지나야 하며, 세 개 이상의 연결선들이 한 점에서 만나서는 안된다.
연결선과 연결선이 만나는 교차점의 개수를 가장 작게 하려고 할 때 최소 교차점의 개수를 구하는 프로그램을 작성하시오.
예를 들어, 점들이 아래 그림과 같이 주어졌다고 하자.
각 점의 위치는 두 개의 양의 정수로 표시된다.
첫째 숫자는 점이 위치한 변을 나타내는데, 1은 윗변, 2는 밑변, 3은 왼쪽 변, 4는 오른쪽 변을 의미한다.
둘째 숫자는 변 위에서의 위치를 나타낸다.
점이 윗변이나 밑변에 있는 경우는 왼쪽 꼭지점부터의 거리를 나타내고, 점이 왼쪽 변이나 오른쪽 변에 있는 경우는 위쪽 꼭지점부터의 거리를 나타낸다.
즉, 점 (4, 7)은 오른쪽 변에 있는 점으로 변의 위쪽 꼭지점으로부터 거리 7만큼 떨어져 있다.
이 그림에서, 두 점(3, 5)와 (4, 7)을 점선과 같이 연결하여, 세 개의 연결선들이 한 점에서 만나게 하면 안된다.
이 그림에서 최소 교차점의 개수는 4이다.
입력
입력의 첫째 줄에는 주어진 점들의 개수가 있다. 단, 점들의 개수는 50을 넘지 않는다.
둘째 줄 이후부터는 각 줄에 모양이 같은 두 점의 위치가 네 개의 숫자로 주어지는데, 첫 번째와 두 번째 숫자가 한 점을 나타내고 세 번째와 네 번째 숫자가 다른 한 점을 나타낸다.
주어진 점들의 위치는 모두 다르다. 각 숫자는 양의 정수이며, 숫자 사이에는 빈칸이 하나 있다.
출력
예제1
10
3 5 4 7
1 7 2 8
2 4 2 7
2 6 4 4
1 5 3 3
4
3