시간 제한
메모리 제한
시간 제한
2초
메모리 제한
128 MB
2차원 평면에 N개의 선분이 주어진다. 각 선분은 두 끝점의 x좌표와 y좌표로 표현된다.
서로 만나는 두 선분은 같은 그룹에 속한다. 여기서 만난다는 것은 선분의 내부에서 교차하는 경우뿐 아니라, 끝점에서 닿거나 한 선분의 끝점이 다른 선분 위에 놓이는 경우도 포함한다.
그룹 관계는 전이된다. 예를 들어 선분 A가 선분 B와 만나고 선분 B가 선분 C와 만나면, A와 C가 직접 만나지 않아도 세 선분은 같은 그룹이다.
주어진 선분들이 몇 개의 그룹으로 나뉘는지와, 가장 큰 그룹에 속한 선분의 개수를 구하라.
첫째 줄에 선분의 개수 N(1 <= N <= 3,000)이 주어진다.
다음 N개의 줄에는 한 선분의 두 끝점 좌표가 x1 y1 x2 y2 순서로 주어진다. 각 좌표의 절댓값은 5,000 이하이며, 한 줄의 값들은 공백으로 구분된다.
첫째 줄에 전체 그룹의 수를 출력한다.
둘째 줄에 가장 큰 그룹에 속한 선분의 개수를 출력한다.