시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 51 21 16 45.714%

문제

직사각형의 변 위에 여러 모양의 점들이 있고, 같은 모양의 점들은 정확히 두 개씩 있다. 단 직사각형의 꼭지점에 놓인 점은 없다. 이제 같은 모양의 두 점들을 직선이나 곡선으로 연결하려고 한다. 연결된 선들은 반드시 직사각형의 내부만을 지나야 하며, 세 개 이상의 연결선들이 한 점에서 만나서는 안된다. 연결선과 연결선이 만나는 교차점의 개수를 가장 작게 하려고 할 때 최소 교차점의 개수를 구하는 프로그램을 작성하시오.

예를 들어, 점들이 아래 그림과 같이 주어졌다고 하자. 각 점의 위치는 두 개의 양의 정수로 표시된다. 첫째 숫자는 점이 위치한 변을 나타내는데, 1은 윗변, 2는 밑변, 3은 왼쪽 변, 4는 오른쪽 변을 의미한다. 둘째 숫자는 변 위에서의 위치를 나타낸다. 점이 윗변이나 밑변에 있는 경우는 왼쪽 꼭지점부터의 거리를 나타내고, 점이 왼쪽 변이나 오른쪽 변에 있는 경우는 위쪽 꼭지점부터의 거리를 나타낸다. 즉, 점 (4, 7)은 오른쪽 변에 있는 점으로 변의 위쪽 꼭지점으로부터 거리 7만큼 떨어져 있다. 이 그림에서, 두 점(3, 5)와 (4, 7)을 점선과 같이 연결하여, 세 개의 연결선들이 한 점에서 만나게 하면 안된다. 이 그림에서 최소 교차점의 개수는 4이다.

입력

입력의 첫째 줄에는 주어진 점들의 개수가 있다. 단, 점들의 개수는 50을 넘지 않는다. 둘째 줄 이후부터는 각 줄에 모양이 같은 두 점의 위치가 네 개의 숫자로 주어지는데, 첫 번째와 두 번째 숫자가 한 점을 나타내고 세 번째와 네 번째 숫자가 다른 한 점을 나타낸다. 주어진 점들의 위치는 모두 다르다. 각 숫자는 양의 정수이며, 숫자 사이에는 빈칸이 하나 있다.

출력

출력의 첫째 줄에는 최소 교차점의 개수를 출력하고, 둘째 줄에 가장 많은 교차점을 갖는 연결선의 교차점 개수를 출력한다.

예제 입력

10
3 5 4 7
1 7 2 8
2 4 2 7
2 6 4 4
1 5 3 3

예제 출력

4
3

힌트