Time limit
2s
Memory limit
128 MB
N line segments are given on a two-dimensional plane. Each segment is described by the x- and y-coordinates of its two endpoints.
Two segments belong to the same group if they meet. Meeting includes crossing in their interiors, touching at an endpoint, or an endpoint lying on the other segment.
Group membership is transitive: if segment A meets segment B and segment B meets segment C, then all three segments are in the same group even if A and C do not meet directly.
Find how many groups the given segments form and how many segments are in the largest group.
The first line contains N (1 <= N <= 3,000), the number of line segments.
Each of the next N lines contains four integers x1 y1 x2 y2, the coordinates of the two endpoints of one segment. The absolute value of every coordinate is at most 5,000. Values on the same line are separated by spaces.
Print the number of groups on the first line.
Print the number of segments in the largest group on the second line.