2697. Beacons

单点时限: 15.0 sec

内存限制: 256 MB

In ancient times, communication was not as swift as it is today. When a kingdom was at war, it could take months to muster all the armed forces. But by using fire-lit beacons at strategic locations, it was still possible to quickly send emergency signals.

When the first beacon is lit, all other beacons within sight from it are also lit. All

beacons within sight of these are then lit, and so on until all beacons are lit - assuming of course that all beacons are within sight of each other, directly or indirectly. If they are not, the dire news must be carried by riders between some beacons.

Given the location of all beacons in the kingdom as well as the location and size of all mountain peaks, write a program that determines how many messages must be sent by

riders in order for all beacons to be lit when an enemy threatens the country.

For simplicity, we model the country in the following way: a beacon is represented as

a point in the xy-plane and a mountain peak is represented as a circle. Two beacons are

considered to be within sight of each other if no mountain peak blocks the straight line

between the two beacons.

The input will be constructed so that the straight line between any pair of beacons will not touch the circumference of a mountain peak, unless it passes through the interior of another mountain peak. Mountain peaks will not overlap or touch, nor will any beacon be on a mountain peak or on its circumference.


The first line in the input contains two integers n (1 <= n <= 1000) and m (0 <= m <= 1000)

the number of beacons and the number of mountain peaks, respectively. Then follow n

lines specifying the locations of the beacons. The location of each beacon is given as a

pair of integers x and y (0 <= x,y <= 10000). Then follow m lines describing the mountain

peaks. Each mountain peak is given as a pair of integers x and y (0 <= x; y <= 10000)

specifying the location of the peak and a radius r (1 <= r <= 5000).


The output should be a single integer: the number of messages that must be carried by

riders for all beacons to be lit.


6 3
1 8
5 4
7 7
9 2
16 6
17 10
4 7 2
6 3 1
12 6 3
4 4
0 4
8 4
4 0
4 8
2 2 1
6 2 1
2 6 1
6 6 1

8 人解决,11 人已尝试。

22 份提交通过,共有 33 份提交。

5.7 EMB 奖励。

创建: 14 年,6 月前.

修改: 6 年,7 月前.

最后提交: 3 年,4 月前.

来源: NCPC 2009