Задачи
Маяки
Маяки
В древние времена средства коммуникации не были настолько быстрыми, как сегодня. Когда царство находится в состоянии войны, сборы всех вооруженных силы может занять несколько месяцев. Однако с помощью пожарных световых маяков в стратегически важных местах можно было быстро отправить сигналы о помощи.
Когда загорается первый маяк, все маяки в пределах его видимости также загораются. Затем загораются маяки в пределах видимости горящих маяков, и так далее, пока не загорятся все маяки - если известно, что все маяки находятся в пределах видимости друг друга, прямо или косвенно. Если это не так, то срочную новость должны передавать всадники между некоторыми маяками.
Вам известно расположение всех маяков в королевстве, а также расположение и размер всех горных вершин. Напишите программу, определяющую количество сообщений, которое необходимо отправить всадниками для зажигания всех маяков, когда враг угрожает стране. Для простоты будем моделировать страну следующим образом: маяк представлен в виде точки на плоскости \textbf{ху}, горная вершина представлена в виде круга. Два маяка находятся в пределах видимости друг друга, если ни одна горная вершина не блокирует прямую линию между ними.
Входные данные будут такими, что никакая прямая линия между любой парой маяков не касается окружности вершины горы, если только при этом она не проходит через внутреннюю часть другого горного пика. Горные вершины не пересекаются и не касаются, никакой маяк не находится на вершине горы или на ее окружности.
\InputFile
Первая строка содержит два числа \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{1000}) и \textbf{m} (\textbf{0} ≤ \textbf{m} ≤ \textbf{1000}) - соответственно количество маяков и количество горных вершин. Следующие \textbf{n} строк задают положение маяков. Положение маяка задается парой целых чисел \textbf{x} и \textbf{y} (\textbf{0} ≤ \textbf{x}, \textbf{y} ≤ \textbf{10000}). Следующие \textbf{m} строк описывают пики гор. Каждый горный пик задается парой целых чисел \textbf{x} и \textbf{y} (\textbf{0} ≤ \textbf{x}, \textbf{y} ≤ \textbf{10000}), задающих местоположение пика и радиус \textbf{r }(\textbf{1 }≤ \textbf{r }≤ \textbf{5000}).
\OutputFile
Вывести количество сообщений, которое необходимо передать всадниками для зажигания всех маяков.
Входные данные #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
Выходные данные #1
2