eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Маяки

Маяки

Ліміт часу 5 секунд
Ліміт використання пам'яті 64 MiB

В древние времена средства коммуникации не были настолько быстрыми, как сегодня. Когда царство находится в состоянии войны, сборы всех вооруженных силы может занять несколько месяцев. Однако с помощью пожарных световых маяков в стратегически важных местах можно было быстро отправить сигналы о помощи.

Когда загорается первый маяк, все маяки в пределах его видимости также загораются. Затем загораются маяки в пределах видимости горящих маяков, и так далее, пока не загорятся все маяки - если известно, что все маяки находятся в пределах видимости друг друга, прямо или косвенно. Если это не так, то срочную новость должны передавать всадники между некоторыми маяками.

Вам известно расположение всех маяков в королевстве, а также расположение и размер всех горных вершин. Напишите программу, определяющую количество сообщений, которое необходимо отправить всадниками для зажигания всех маяков, когда враг угрожает стране. Для простоты будем моделировать страну следующим образом: маяк представлен в виде точки на плоскости ху, горная вершина представлена в виде круга. Два маяка находятся в пределах видимости друг друга, если ни одна горная вершина не блокирует прямую линию между ними.

Входные данные будут такими, что никакая прямая линия между любой парой маяков не касается окружности вершины горы, если только при этом она не проходит через внутреннюю часть другого горного пика. Горные вершины не пересекаются и не касаются, никакой маяк не находится на вершине горы или на ее окружности.

Вхідні дані

Первая строка содержит два числа n (1n1000) и m (0m1000) - соответственно количество маяков и количество горных вершин. Следующие n строк задают положение маяков. Положение маяка задается парой целых чисел x и y (0x, y10000). Следующие m строк описывают пики гор. Каждый горный пик задается парой целых чисел x и y (0x, y10000), задающих местоположение пика и радиус r (1 r 5000).

Вихідні дані

Вывести количество сообщений, которое необходимо передать всадниками для зажигания всех маяков.

Приклад

Вхідні дані #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
Джерело 2009 Nordic Collegiate Programming Contest, Жовтень 3, Задача H