[Login|Register]
Problems

Status

Rank

Problem 1291
Segments
Time Limit: 2000ms
Memory Limit: 65536kb
Description
There 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.
Input
The 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.
1<=N<=50
-10000<= x1, y1, x2, y2<= 10000
No the condition: x1==x2&&y1==y2.
Notice: Any two lines would not totally coincide.
Output
Output the maximum of X?
Sample Input
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
Sample Output
2
4   
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.5ms with 1 query(s).