DMPG '17 G5 - Vera and Pets

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem types

Vera has a yard in the shape of a rectangle with corners at (0,0) and (X,Y) that is surrounded by a fence. She owns a cat who lives in a kitty house at (0,0) and a rabbit who lives at (X,Y). Her cat is evil and would eat the rabbit at night if given the chance. To protect her rabbit, Vera will install some lamps that will light up the yard at night. The cat is irrationally scared of lights and will not dare to enter any area that is lit by a lamp.

There are N possible lamps that Vera can install. The i-th lamp, if installed, will light an area in the shape of a circle with center (x_i,y_i) and radius r_i. Consider the cat as a point. The cat will be able to eat the rabbit if there exists a path from (0,0) to (X,Y) that remains inside the yard and does not touch or intersect the area lit by any lamp.

It is acceptable to install a lamp that covers (0,0), in which case the cat will not be able to move anywhere as it cannot leave its kitty house.

There may be multiple possible lamps at the same point.

Vera does not want the lit area to be too big, so she would like to find a subset of the lamps to install such that her cat won't eat her rabbit and the total area lit by any lamp is minimum. This includes any area outside the yard that is lit by a lamp. Determine the minimum possible area of a valid installation of lamps.

It is possible that installing all the lamps will not stop the cat, in which case output 0.

Constraints

  • 1 \le N \le 1000
  • 1 \le X,Y, r_i \le 500
  • 0 \le x_i \le X
  • 0 \le y_i \le Y
  • All input are integers

Input Specification

N X Y

x_1 y_1 r_1

\vdots

x_N y_N r_N

Output Specification

Output one line with the minimum possible area.

If the cat cannot be stopped, output one line with 0.

Your answer will be considered correct if its absolute or relative error does not exceed 10^{-4}.

Sample Input 1

3 6 3
2 3 3
3 0 2
4 2 1

Sample Output 1

14.7462241

Explanation of Sample Output 1

Vera can install the second and third lamps. Installing the first lamp is a less optimal solution as it has an area of 28.2743338.

Sample Input 2

2 3 4
0 2 1
3 2 1

Sample Output 2

0

Explanation of Sample Output 2

Installing both lamps will not stop the cat.


Comments

There are no comments at the moment.