SERCOVERAGE - Coverage

A cellular provider has installed n towers to support their network. Each tower provides coverage in a 1km radius, and no two towers are closer than 1km to each other. The coverage region of this network is therefore the set of all points that are no more than 1km 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 1km of an existing tower. Given that the provider is able to build one more tower, what is the maximum number of towers (including the new one) that can be included within a single connected subregion of coverage?

Input

Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The first line of input consists of a single integer n (1≤n≤5,000) denoting the number of existing towers. Next follow n lines, each with 2 space separated floating-point numbers x and y (0≤x,y≤100,000), denoting the location of a tower in km. It will be guaranteed that the optimal number of towers will not change even if the coverage radius of all the towers is increased or decreased by 10-6 km.

Output

Ouput 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

Input:
5 
1.0 1.0
3.1 1.0
1.0 3.1
3.1 3.1
4.2 3.1 Output: 6

Added by:Joshua Kirstein
Date:2016-03-29
Time limit:3s-15s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:ACM SER 2015

hide comments
2016-04-18 13:59:47
Finally AC with O(n^3) with heavy pruning and optimisation!!!!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.