The well-known game development company "Clissard Entertainment" has released
new Action-RPG game named "Angel VII". Vasya has bought this game and played
a lot until he entered the "The Secret Cow Level". This secret was covered by
Clissard for a long time, but eventually fans has guessed the mysterious notes
like "Moo" strings appearing in the game chat.
The cow level is infinite in all directions plane with Vasya (a point) and
N cows (circles of equal radius R). Vasya is playing as a bowazon — amazon with a bow.
His character knows a useful skill called "Multiple shot". It is used in the
following way: Vasya chooses a direction which we will call the main direction.
The bow splits one arrow into K arrows and shoots them. The i-th arrow (counting from zero)
subtend the angle Ai with the main direction equal to:
Each arrow flies along a straight line (arrow is also a point). Crossing or touching
a cow is considered as a hit. Thanks to a passive skill "Pierce" an arrow after the hit
has a chance P to pierce target and continue its path and a chance 100% − P
to get stuck in the cow or just break. However, there is a cap on this skill: each arrow can't hit
more than five targets. After hitting fifth target it disappears for sure. Vasya is
surrounded by cows now and he has to shoot immediately without moving. Help Vasya to
choose the main direction to maximize the expectation value of number of hits!
The cows don't move and are very tough so every hit to a single cow should be counted.
Cows and Vasya don't intersect or touch each other (cows also can't lie one in the other).
In the first line four numbers are written:
N (integer number of cows), K (integer number of arrows),
P (integer pierce probability in percent), R (real radius of cows)
In the second line two coordinates of Vasya are written (both real).
Then N lines follow: each line consists of two real numbers — coordinates of the cow
(1 ≤ N ≤ 50000; 2 ≤ K ≤ 16; 0 ≤ P ≤ 100; 0.4 ≤ R ≤ 2.0). Absolute values of all coordinates don't exceed 25000.
The only line must be the normalized direction (two coordinates with at least 10 digits, sum of their squares must be equal to 1.0)
and the expectation value with four digit precision. See output format in the example below.
3 5 40 1.0
The best shot at (0.8944271910;0.4472135955) gives Vasya 5.8000 average hits.
Источник задачи: Novosibirsk SU Contest. Petrozavodsk training camp, September 2007