<?xml version="1.0" encoding="Windows-1251"?>
<CATS version="1.0">
<Problem title="Radio Coverage" lang="en" author="B. Vasilyev, A. Klenin" tlimit="5" mlimit="4"
    inputFile="input.txt" outputFile="output.txt" stdChecker="floats2">

<Picture name="circ" src="circ.gif"/>
<ProblemStatement>

<p>
<img picture="circ" align="right"/>
Radio station 'ACM Rock' is broadcasting over the circular area with center in point
(<i>x</i><sub>0</sub>, <i>y</i><sub>0</sub>) and radius <i>R</i>.
In order to increase the auditorium, it were suggested to build several relay stations.
<i>N</i> locations were selected as candidate sites for relay stations.
Relay station placed in <i>i</i>-th location will cover a circular area with center
 in point (<i>x<sub>i</sub></i>, <i>y<sub>i</sub></i>) and radius <i>r<sub>i</sub></i>,
 where center lies inside the area covered by the base station,
 (<i>x</i><sub>0</sub> - <i>x<sub>i</sub></i>)<sup>2</sup> +
 (<i>y</i><sub>0</sub> - <i>y<sub>i</sub></i>)<sup>2</sup> &amp;le; <i>R</i><sup>2</sup>.
</p>
<p>
  Your task is to select a subset of sites for relay stations so that:
  <ol>
    <li>the covered areas for relays do not intersect (but may touch) one another,</li>
    <li>the total area covered by base station and all relays is maximum possible.</li>
  </ol>
</p>
</ProblemStatement>

<InputFormat>
Input file contains integer number <i>N</i> followed by real numbers
  <i>x</i><sub>0</sub> <i>y</i><sub>0</sub> <i>R</i>, followed by <i>N</i>
  triples of real numbers <i>x<sub>i</sub></i> <i>y<sub>i</sub></i> <i>r<sub>i</sub></i>.
</InputFormat>

<OutputFormat>
Output file should contain a single real number -- the maximal coverage area with the
absolute error less than 10<sup>&amp;minus;2</sup>.
</OutputFormat>

<ProblemConstraints>
1 &amp;le; <i>N</i> &amp;le; 10,
0 &amp;le; <i>x<sub>i</sub></i>, <i>y<sub>i</sub></i>,
  <i>x</i><sub>0</sub>, <i>y</i><sub>0</sub> &amp;le; 1000,
1 &amp;le; <i>r<sub>i</sub></i> &amp;le; <i>R</i> &amp;le; 1000.
</ProblemConstraints>

<Sample rank="1">
  <SampleIn>1 0 0 10
10 0 10</SampleIn>
  <SampleOut>505.4816</SampleOut>
</Sample>

<Solution name="sol" src="rock.dpr"/>
<Solution name="sol1" src="bd.dpr"/>
<TestRange from="1" to="9"><In src="%0n.txt"/><Out use="sol"/></TestRange>

</Problem>
</CATS>