Time Limit: 2000ms
Memory Limit: 65536kb
DescriptionThere are N segments in the 2D plane. Assuming you can find a line to intersect with X segments. Can you tell me the maximum of X?
The definition of a line and a segment’s intersection: there existing one point at least which lies to the line and the segment simultaneously.
For example, the second data’s case is as follows and the blue line is our aim line and it intersects with four segments.
InputThe first line, an integer T (1<=T<=20), indicates test case numbers. For each case:
The first part: an integer N indicating the numbers of segments.
The second part: N lines with each line four integer numbers x1, y1, x2, y2.
-10000<= x1, y1, x2, y2<= 10000
No the condition: x1==x2&&y1==y2.
Notice: Any two lines would not totally coincide.
OutputOutput the maximum of X?
2 2 1 1 2 2 3 3 4 4 4 0 3 3 3 2 2 3 2 1 1 2 1 0 0 1 0