ZOJ Problem Set - 3570
Long long ago, the evil Dragon reborned from the hell and attempted to control the world. Brave Lott experienced lots of hardships and finally reached the castle of the Dragon. After a fierce battle, the Drangon used the magic power to create countless images, and there are straight ways (lines) between any different images. In order to reseal the Dragon back to the underground, Lott launched the "Spellbinding Circle" creating a Hexagram to limit the movement of the Dragon.
NOTE: images are regarded as points.
The Hexagram is composed of two equilateral triangles, just as the same shape in the picture below. We say R in the picture is the radius of the Hexagram.
More precisely, Lott must create a Hexagram area with centre in his own place to cover all lines between any two images. At the same time, it must also follow the rule that useless area is bigger than given S. Useless area are defined as the area in the Hexagram not covered by the area surrounded by the images.
As we know, we have the same position of Lott and Dragon with (X, Y). And we know the number of the images m, with their positions (X1, Y1), (X2, Y2) ... (Xm, Ym). The centre of the Hexagram is Lott(X,Y), The Hexagram will not be able to move or rotate, that is, the Hexagram's center must be (X, Y) and the angles are just like what the picture shows.
Now, we want to know the result of the seal. We say the seal is successful if the the Hexagram is big enough to cover all lines between images and the useless area is bigger than S.
There are multiple cases in this problem.
In the first line for each case, there are two integers representing the position of Lott and Dragon: X and Y.(-50000 <= X, Y <= 50000).
In the second line contains one integer representing the number of Dragon's images m. (3 <= m < = 100000).
Then following m lines, each line contains two integers representing the position of one image Xi and Yi (-50000 <= Xi, Yi <=50000).
And in the last line contains one integer R representing the radius of the Hexagram, and a float number S representing the minimum useless area of the Hexagram (1 <= R <= 10000, 0 <= S <= 10^9).
In each case, output one line of "Failed." if the seal failed or "Succeeded." if Lott make a success.
0 0 3 2 -1 -2 -1 0 3 2 12.78
Author: XIONG, Siyuan
Contest: ZOJ Monthly, December 2011