Problems
Beacons
Beacons
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.
\InputFile
The first line contains two integers \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{1000}) and \textbf{m} (\textbf{0} ≤ \textbf{m} ≤ \textbf{1000}) the number of beacons and the number of mountain peaks, respectively. Then follow \textbf{n} lines specifying the locations of the beacons. The location of each beacon is given as a pair of integers \textbf{x} and \textbf{y} (\textbf{0} ≤ \textbf{x}, \textbf{y} ≤ \textbf{10000}). Then follow \textbf{m} lines describing the mountain peaks. Each mountain peak is given as a pair of integers \textbf{x} and \textbf{y} (\textbf{0} ≤ \textbf{x}, \textbf{y} ≤ \textbf{10000}) specifying the location of the peak and a radius \textbf{r} (\textbf{1} ≤ \textbf{r} ≤ \textbf{5000}).
\OutputFile
Print a single integer: the number of messages that must be carried by riders for all beacons to be lit.
Input example #1
50 30 356 551 327 188 299 680 457 993 608 89 122 120 102 613 438 119 80 533 249 800 460 921 474 195 23 97 1 983 110 732 137 1 961 157 623 990 862 949 15 569 788 119 873 539 379 866 205 534 261 615 892 651 239 377 509 773 270 496 368 244 445 294 325 786 931 912 337 192 642 572 637 570 647 999 877 710 859 562 778 426 907 803 816 864 482 101 839 823 283 630 772 91 263 12 541 522 851 896 360 756 718 619 60 958 988 55 630 927 49 476 540 53 988 642 71 16 653 51 216 71 49 496 846 65 30 862 80 848 991 41 531 57 51 170 644 73 514 352 80 726 817 71 118 273 77 324 420 79 820 222 47 677 314 73 896 86 74 558 206 62 559 655 53 937 294 61 273 291 59 194 878 73 632 469 80 906 442 80 516 970 43 678 93 46 187 453 52 30 381 54
Output example #1
2