ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Novosibirsk SU contest. Petrozavodsk training camp. Summer 2007

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

E. Multishot in the Secret Cow Level

Ограничение времени: 5.0 секунды
Ограничение памяти: 64 МБ
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.
Источник задачи: Novosibirsk SU Contest. Petrozavodsk training camp, September 2007
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1556. Multishot in the Secret Cow Level