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

Novosibirsk SU contest. Petrozavodsk training camp. Summer 2007

About     Problems     Submit solution     Judge status     Standings
Contest is over

E. Multishot in the Secret Cow Level

Time limit: 5.0 second
Memory limit: 64 MB
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:
Problem illustration
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!
Problem illustration
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
-2.0 1
0 2.0
3 2.0
4 -3
The best shot at (0.8944271910;0.4472135955) gives Vasya 5.8000 average hits.
Problem Source: Novosibirsk SU Contest. Petrozavodsk training camp, September 2007
To submit the solution for this problem go to the Problem set: 1556. Multishot in the Secret Cow Level