프로그램 명: ncross
제한시간: 10 초

직사각형의 변 위에 여러 모양의 점들이 있고 같은 모양의 점들은 정확히 두 개씩 있다.단 직사각형의 꼭지점에 놓인 점은 없다.

이제 같은 모양의 두 점들을 직선이나 곡선으로 연결하려고 한다. 연결된 선들은 반드시 직사각형의 내부만을 지나야 하며 세 개 이상의 연결선들이 한 점에서 만나서는 안된다.

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

예를들어 점들이 아래 그림과 같이 주어졌다고 하자. 각 점의 위치는 두 개의 양의 정수로 표시된다.

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

즉, 점(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 초등 기출

[질/답] [제출 현황] [푼 후(0)]
[ 채 점 ] [홈으로]  [뒤 로]