#616선분 그룹

기초
⏱ 시간 제한: 2|💾 메모리 제한: 128 MB

문제 설명

N개의 선분들이 2차원 평면상에 주어져 있습니다. 선분은 양 끝점의 x, y 좌표로 표현이 된다.

두 선분이 서로 만나는 경우에, 두 선분은 같은 그룹에 속한다고 정의하며, 그룹의 크기는 그 그룹에 속한 선분의 개수로 정의합니다. 두 선분이 만난다는 것은 선분의 끝점을 스치듯이 만나는 경우도 포함하는 것으로 합니다.

N개의 선분들이 주어졌을 때, 이 선분들은 총 몇 개의 그룹으로 되어 있을까? 또, 가장 크기가 큰 그룹에 속한 선분의 개수는 몇 개일까? 이 두 가지를 구하는 프로그램을 작성해 보자.

입력 설명

첫째 줄에 N(1 ≤ N ≤ 3,000)이 주어집니다. 둘째 줄부터 N+1번째 줄에는 양 끝점의 좌표가 x1, y1, x2, y2의 순서로 주어집니다. 각 좌표의 절댓값은 5,000을 넘지 않으며, 입력되는 좌표 사이에는 빈칸이 하나 있습니다.

출력 설명

첫째 줄에 그룹의 수를, 둘째 줄에 가장 크기가 큰 그룹에 속한 선분의 개수를 출력합니다.

예제

입력 1

3
0 0 4 4
0 4 4 0
5 5 6 6

출력 1

2
2

관련 태그

언어:

테스트 실행 결과가 여기에 표시됩니다

제출하려면 로그인이 필요해요