Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1004. Radio Coverage
ГеометрияОлимпиадные задачи на английском языке
| 03/07/2008 | Лето 2008 дорешивание ( 8I) |
| 18/07/2008 | Лето 2008 - 8 (I) |
Ограничения: время – 2s/4s, память – 16MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Radio station 'ACM Rock' is broadcasting over the circular area with center in point
(`x_0`, `y_0`) and radius `R`.
In order to increase the auditorium, it were suggested to build several relay stations.
`N` locations were selected as candidate sites for relay stations.
Relay station placed in `i`-th location will cover a circular area with center
in point (`x_i`, `y_i`) and radius `r_i`,
where center lies inside the area covered by the base station,
`(x_0\ -\ x_i)^2\ +\ (y_0\ -\ y_i)^2\ ≤\ R^2`.
Your task is to select a subset of sites for relay stations so that:
- the covered areas for relays do not intersect (but may touch) one another,
- the total area covered by base station and all relays is maximum possible.
Input
Input file contains integer number `N` followed by real numbers
`x_0` `y_0` `R`, followed by `N` triples of real numbers `x_i` `y_i` `r_i`.
Output
Output file should contain a single real number – the maximal coverage area with the
absolute error less than `10^{-2}`.
Constraints
`1\ ≤\ N\ ≤\ 10`,
`0\ ≤\ x_i,\ y_i,\ x_0,\ y_0\ ≤\ 1000`,
`1\ ≤\ r_i\ ≤\ R\ ≤\ 1000`.
Sample Input
1 0 0 10 10 0 10
Sample Output
505.4816
