Имя: Пароль: Зарегистрироваться Восстановить пароль
08/09/2024 10:47:40

# Рабочее место участника

## Задачи

Ограничения: время – 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

Source: B. Vasilyev, A. Klenin, ICPC NEERC Far-Eastern subregional, 2004