Given a lake, a central island, and S unit rocks, find the minimum leap distance letting Vlad reach the island and return twice without landing on any rock twice.
Hard9Binary searchGraphGeometryBFSNo attempts yetTime limit8sMemory limit512 MBA circular lake of radius L has a circular island of radius R at its exact center, and the water is full of crocodiles. There are S round stones of radius 1 resting in the water.
Vlad the impala has to pass the herd's leadership challenge. He starts on the outer edge of the lake, reaches the island, returns to the outer edge, reaches the island a second time, and returns to the outer edge again. He moves only by leaping, and touching the water ends the attempt on the spot. He may leap from the exact edge of one object to the exact edge of another, he may turn as sharply as he likes between leaps, and he may leap over a stone without landing on it.
Crocodiles grab an impala standing on a stone, but they cannot reach the island or the outer edge. They never grab an impala from a stone it is standing on for the first time, so Vlad is safe exactly when he never lands on the same stone twice during the whole challenge. The island and the outer edge may be used as often as he likes.
Vlad can leap any distance up to his maximum leap distance, as many times as he wants. Let d be the smallest maximum leap distance that lets him finish the challenge safely. Vlad wants an integer, so print ⌈d⌉. If he has to be able to leap at least 2.01, the answer is 3.
The first line contains three integers L, R, and S: the radius of the lake (4≤L≤109), the radius of the island (1≤R≤L−3), and the number of stones (4≤S≤1000).
Each of the next S lines contains two integers x and y, the coordinates of one stone's center with the center of the lake as the origin (∣x∣≤109, ∣y∣≤109). Every stone lies fully in the water. A stone may touch another stone, the island, or the outer edge of the lake, but no two of these objects overlap.
Print one integer, the value ⌈d⌉. The distance Vlad needs is always positive.