Beacons#549
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. However, by using fire-lit beacons at strategic locations, it was possible to quickly send emergency signals.
When the first beacon is lit, all beacons within sight of it are also lit. Then, beacons within sight of these are lit, and so on, until all beacons are lit—assuming that all beacons are within sight of each other, directly or indirectly. If this is not the case, riders must carry the urgent message between some beacons.
You are given the locations of all the beacons in the kingdom, as well as the locations and sizes of all the mountain peaks. Write a program that determines how many messages must be carried by riders in order for all beacons to be lit when an enemy threatens the country. For simplicity, we will model the country as follows: a beacon is represented as a point in the -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 them.
The input will be constructed in such a way that the straight line between any pair of beacons does not touch the circumference of any mountain peak, unless it passes through the interior of another mountain peak. Mountain peaks do not overlap or touch each other, and no beacon is located on a mountain peak or on its circumference.
The first line contains two integers (1 \le n \le 1000) and (0 \le m \le 1000) — the number of beacons and the number of mountain peaks, respectively. The next lines specify the locations of the beacons. The location of each beacon is given as a pair of integers and (0 \le x, y \le 10000). The next lines describe the mountain peaks. Each mountain peak is given as a pair of integers and (0 \le x, y \le 10000) specifying the location of the peak and a radius (1 \le r \le 5000).
Print a single integer: the number of messages that must be carried by riders for all beacons to be lit.
Example 1