Подразделы

Другие разделы

09/04/2025 16:42:28

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

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

03/07/2008	Лето 2008 дорешивание ( 8I)
18/07/2008	Лето 2008 - 8 (I)