题目描述

 “ACM摇滚” 广播电台在以点((x_0, y_0))为圆心、半径为(R)的圆形区域内进行广播。为了扩大听众群体，有人建议建造几个中继站。已经选定了(N)个位置作为中继站的候选地点。放置在第(i)个位置的中继站将覆盖一个以点((x_i, y_i))为圆心、半径为(r_i)的圆形区域，其中圆心位于基站覆盖的区域内，即 (x0 - xi)² + (y0 - yi)² ≤ R².

你的任务是选择一个中继站位置的子集，使得：

1.中继站的覆盖区域彼此不相交（但可以相切）；

2.基站和所有中继站覆盖的总面积尽可能大.

输入

输入包含一个整数(N)，接着是实数(x_0) (y_0) (R)，然后是(N)组三个实数(x_i) (y_i) (r_i)。

1 ≤ N ≤ 10, 0 ≤ xi, yi, x0, y0 ≤ 1000, 1 ≤ ri ≤ R ≤ 1000。

输出

输出应该包含一个实数 —— 最大覆盖面积，绝对误差小于10⁻²。

1 0 0 10
10 0 10

505.4816

来源

2004年东北欧，远东分区赛