线段相交

Time Limit: 10000/5000MS (Java/Others) Memory Limit: 512000/256000KB (Java/Others)

Problem 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: at least existing one point lies the line and the segment simultaneously.

Input

The first line, an integer T (1<=T<=20), indicating 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

Hint

Source

Dshawn

Manager

Information
Solved Number83
Submit Number274
Problem Tags
geometry
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel