覆盖问题

★问题描述：

通信公司准备在n 个村庄中的某些村庄安装基站,对于村庄i ，在其中建立基站的花费

是Ci。我们把村庄看成是一个二维平面上的点。对于每一个基站，他们的规格，配置都是

相同的，一个基站发射的信号可以覆盖以它为中心的半径为R 米的圆形区域(边界上的也

算被覆盖)。现在公司希望用最小的花费，使得这n 个村庄都能被信号覆盖。

★实验任务：

对于给定的村庄的位置和修建基站的信息，求出公司覆盖所有村庄的最小花费。

★数据输入：

第一行是一个整数n（1<=n<=20）代表给定的村庄个数。

接下来n 行，每行有3 个整数xi yi ci, 分别表示村庄的坐标以及在第i 个村庄修建

基站的花费。(0<= xi, yi, ci <= 100)

最后一行是一个整数R , 表示基站的覆盖范围。(0 <= L <= 100)

★结果输出：

公司覆盖所有村庄的最小花费。

输入:

3

0 0 1

1 0 2

1 1 4

1

输出:

2-Cover problem

★ Problem Descr iption :

Communications ready n villages installation of base stations in certain villages , the village i, in which the base station to establish spending

Is Ci. We village as a point on a two-dimensional plane . For each base station , their specifications , configurations are

Same , the base station transmits a signal which can be covered with the center of the circular area of radius R m ( also the boundary

Operators covered) . Now the company hopes to use the smallest cost , making this n villages can be overwritten signal.

★ experimental tasks :

For information given the location and construction of the village station , find the minimum cost companies covering all the villages.

★ Data input :

The first line is an integer n (1 <= n <= 20) representative of a given number of villages.

The next n lines, each line has three integers xi yi ci, denote the coordinates of the village and the village built in the i-th

Takes the base station.