ADAPICK - Ada and Cucumber


Ada the Ladybug works as farmer. Its season of cucumbers and she wants to harvest them. There lies many cucumbers all around her house. She wants to choose a direction and follow it until all cucumbers in that direction are collected.

Lets consider Ada's house as centerpiece of whole universe, lying on [0,0]. The cucumbers are defined as lines on plane. No cucumber goes through Ada's house (and no cucumber touches it).

How many cucumbers can Ada pick in one go if she chooses the best direction possible?

Input

The first line contains an integer T, the number of test-cases.

Each test-case begins with an integer 1 ≤ N ≤ 105

Afterward N lines follow, with four integers -106 ≤ x1,y1,x2,y2 ≤ 106, the beginning and end of each cucumber. Each cucumber has positive length.

Sum of all N over all test-cases won't exceed 106

Even though cucumber will not go through house, they might touch, intersect or overlap other cucumbers!

Output

For each test-case print one integer - the maximal number of cucumbers which could be picked if Ada chooses a direction and picks every cucumber lying in it.

Example Input

5
4
2 1 -1 4
-2 1 1 3
-3 2 0 5
-2 -2 5 1
3
-2 2 -2 -2
2 2 2 -2
-3 -3 -6 -3
3
-2 1 -3 4
3 1 5 5
-2 -2 2 -2
6
-1 5 -6 5
-3 -3 5 -3
-2 -5 5 -5
-1 -6 5 -6
5 1 5 5
6 6 6 -11
3
1 3 4 3
4 2 4 -1
5 1 6 6

Example Output

3
2
1
4
2

Possibly harvested cucumbers

1 2 3
1 3
1
2 3 4 6
2 3

hide comments
kauai68: 2020-04-25 14:08:09

Angular sweep with integer arithmetic works. I've got WA for a long time, because my abort criterium of the angular sweep was wrong. The following test case with solution 6 helped me to solve the problem:

1
10
-929239 -852357 833305 -466785
-538306 -671440 911964 589315
-141573 -21504 834625 442765
702682 838131 -963327 -600809
937567 -486734 129193 -277691
906000 -830536 -953093 845426
-126429 622401 969267 725994
276207 -270532 911853 -576117
-248762 -752060 -452293 -348503
731135 436907 -219800 -599169

Last edit: 2020-04-25 14:17:32
:D: 2019-10-08 23:26:49

Small hint: this problem can and should be solved without using floating point operations. Only integer arithmetic. Otherwise precision issues will probably result in WA.

narek: 2018-08-09 16:08:43

Have been trying for two days on this one.. I can't find any test case where my solution gives a wrong answer :(

Edit.. came back after one year.. same results lol

Edit2: Okay a couple years later.. problem solved.

Hint: Think about segments that have a big angle with the origin.
- Also math funcrtoins are slow, if you are using math library make sure not to recompute the same thing multiple times.

Last edit: 2024-07-02 16:49:05
the193thdoctor: 2018-04-24 08:42:14

I keped WA,can sombody help me?


Added by:Morass
Date:2017-02-12
Time limit:2.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All