UVa 10310

From Algorithmist
Jump to: navigation, search

10310 - Dog and Gopher[edit]

10310 - Dog and Gopher

Summary[edit]

Given the coordinates of the dog, the gopher and the holes, you are asked to check whether the gopher can escape from the dog through the holes.

Explanation[edit]

Use the Pythagoras Theorem to find the distance from the dog to the hole, and from the gopher to the hole. Let G be the distance of the gopher to the hole, and D be the distance of the dog to the hole. If D\geq 2G the gopher can escape through that hole. If there are 2 holes that satisty this condition, output the one that appears first in the input.

Input[edit]

1 1.000 1.000 2.000 2.000
1.500 1.500

2 2.000 2.000 1.000 1.000
1.500 1.500
2.500 2.500

2 1.000 0.000 2.000 0.000
0.000 0.000
0.500 0.000

Output[edit]

The gopher cannot escape.
The gopher can escape through the hole at (2.500,2.500).
The gopher can escape through the hole at (0.000,0.000).