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