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.
Input
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 (Xi, Yi) — 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.
Output
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”.
Samples
input | output |
---|
4
0 0
0 1
1 1
1 0
1 3
| 0.500000 -1.000000
|
3
0 0
0 14
2 7
8 10
| No solution
|
Problem Author: Alex Samsonov
Problem Source: Ural SU Contest. Petrozavodsk Winter Session, January 2008