eolymp
bolt
Try our new interface for solving problems
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.
Time limit 5 seconds
Memory limit 64 MiB
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
Source 2009 Nordic Collegiate Programming Contest, October 3, Problem H