Internet Cable
Time limit4sMemory limit256 MB
Choose a line and a distance d so that as many given points as possible lie exactly at distance d from the line; output that maximum count.
- Level
Hard8 of 10
- Topics
- Geometry, Math, Hash map, Brute force
- Solved
- No attempts yet
Problem
The internet service provider Jota, popular in Flatland, decided to expand its reach. To do this, Jota plans to lay a new internet cable. The internet cable can be thought of as a line in the plane.
Jota knows that Flatland has n potential subscribers, the i-th subscriber lives in a house at coordinates (xi, yi), and no more than one subscriber lives in a single house. The internet cable can be configured to provide internet to all subscribers that are exactly at some chosen distance from it. In other words, if the internet cable is configured at distance d, it provides internet to those and only those subscribers whose house point has Cartesian distance d to the line representing the internet cable.
Help Jota's engineers install the internet cable so that the number of subscribers covered by it is maximal.
Input
The first line contains a single positive integer t, the number of test cases in the input. The descriptions of the test cases follow.
The description of each test case consists of several lines. The first line contains a single integer n (1 ≤ n ≤ 10³), the number of subscribers.
The next n lines contain two integers xi, yi each (−10⁹ ≤ xi, yi ≤ 10⁹), the coordinates of the i-th subscriber. It is guaranteed that no two subscribers' houses are at the same point.
The sum of n over all test cases does not exceed 10³.
Output
Print a single integer, the maximum number of subscribers Jota can cover.