|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|3 초||256 MB||21||12||7||43.750%|
A cellular provider has installed n towers to support their network. Each tower provides coverage in a 1 km radius, and no two towers are closer than 1 km to one another. The coverage region of this network is therefore the set of all points that are no more than 1 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 1 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 n (1 ≤ n ≤ 5,000), denoting the number of existing towers. Next follow n lines each with 2 space-separated real numbers xi, yi (0 ≤ xi, yi ≤ 105), denoting the location of tower i 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, on a single line, 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.
5 1.0 1.0 3.1 1.0 1.0 3.1 3.1 3.1 4.2 3.1
5 1.0 1.0 3.1 1.0 1.0 3.1 3.1 3.1 10.0 10.0