print1004. Radio Coverage

printRadio Coverage

Ограничения: время – 2s/4s, память – 16MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение 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
loading