ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural SU contest. Petrozavodsk training camp. Winter 2008

About     Problems     Submit solution     Judge status     Standings
Contest is over

C. Goat in the Garden 6

Time limit: 0.5 second
Memory limit: 64 MB
The war between neighbors Vasiliy Petrovich and Petr Vasilyevich was in progress for already seven years. Nobody remembers now, when it has started. Nobody can say for sure, who of the neighbors was the first to find a goat in his garden with cabbage. But since that, if any of them leaves for a moment, the other one immediately leads his goats to his neighbor's garden. Both Vasiliy Petrovich and Petr Vasilyevich became accustomed to this fact, and another ravaged cabbage bed doesn't surprise any of the neighbors.
Ivan Ivanovich decided to make use of this old enmity. Once Petr Vasilyevich didn't lend money to him, and it was time to take revenge for this nasty behavior. Ivan Ivanovich waited until Petr Vasilyevich left for the city on business and after that he led his goat to Petr Vasilyevich's garden (hoping, that when Petr Vasilyevich would notice the eaten cabbage, he would accuse Vasiliy Petrovich's goats).
When Ivan Ivanovich came to the garden, he found out that there was only one cabbage bed left, and a little goat kid of Vasiliy Petrovich was already grazing there. Ivan Ivanovich decided to put a peg into the ground and bound his goat and the kid of Vasiliy Petrovich to it in such a way, that his goat would be able to reach any point of the bed, and the kid wouldn't be able to reach any inner point of the bed. It is known, that the length of the rope for the goat is equal to R, and the length of the rope for the kid is equal to r. Help Ivan Ivanovich to find the necessary place for the peg.


The bed is a convex polygon with N vertices. The first line contains an integer N (3 ≤ N ≤ 50). The following N lines contain the coordinates of the vertices of the polygon (XiYi) — integers with absolute values not exceeding 1000. The vertices are listed in the order of traversal. The last line contains integers r and R. 1 ≤ r < R ≤ 1000. The sizes of the peg, the goat, and the kid shouldn't be taken into account.


If there is a way to bind the goat and the kid, output a pair of numbers — coordinates of the place for a peg. The numbers should be rounded to 10−6. If there is no such way, output “No solution”.


0 0
0 1
1 1
1 0
1 3
0.500000 -1.000000
0 0
0 14
2 7
8 10
No solution
Problem Author: Alex Samsonov
Problem Source: Ural SU Contest. Petrozavodsk Winter Session, January 2008
To submit the solution for this problem go to the Problem set: 1662. Goat in the Garden 6