Coverage#8189
A cellular provider has installed towers to support their network. Each tower provides coverage in a km radius, and no two towers are closer than km to one another. The coverage region of this network is therefore the set of all points that are no more than km away from at least one tower. The provider wants as much of this region as possible to be connected, in the sense that a user at any point within a connected subregion can travel to any other point within the connected subregion without having to exit the subregion. Their current installation of towers may or may not already form a single connected region, but they have the resources to build one more tower wherever they want, including within km of an existing tower.
Given that the provider is able to build one more tower, what is the maximum number of towers (including the one just built) that can be included within a single connected subregion of coverage?
The first line consists of a single integer (1 \leq n \leq 5000), denoting the number of existing towers. Next follow lines each with space-separated real numbers x_i, y_i (0 \leq x_i, y_i \leq 10^5), denoting the location of tower in km. It is guaranteed that the optimal number of towers will not change even if the coverage radius of all the towers is increased or decreased by one millimeter.
Print a single integer denoting the maximum number of towers that can be within a single connected subregion of the network after installing one additional tower.
Example 1
Example 2