P0515

[Ncpc2009]Beacons

[Ncpc2009]Beacons

在远古时代，信息的交流没有我们现在这么便利。一个国家在战争时期，可能花好几个月的时间来集合军队。但是在作战区用上烽火台，就有可能快速地传递军事信号。

当第一个烽火台被点燃，所有能看到这个烽火台的其他烽火台也将被点燃，所有能看到这些烽火台的其他烽火台也将被点燃，如此继续直到所有烽火台都被点燃——自然，这要求所有的烽火台都直接或间接地在彼此的视野范围内。如果不是这样，则紧急的信息必须由骑手们在一些烽火台间传递。

给出这个国家所有烽火台的位置，同时还给出山峰的位置和大小，请写一个程序来决定：为使敌人入侵这个国家时所有的烽火台都被点燃，有多少信息要被骑手们传递。

简单来说，我们这样来定义一个国家的模型：一个烽火台就用 xyxy 平面上的一个点来表示，一座山峰就用一个圆来表示。如果两个烽火台的连接直线上没有山峰座落，则认为这两个烽火台是在相互的视野内。

输入是这样构造的：

  • 任何一对烽火台的连线不会与山峰的圆周相切，除非这条连线通过了别的山峰的内部；
  • 山峰不会重叠或相切；
  • 任何一个烽火台也不会在山峰内或它的圆周上。

输入格式

第一行有两个整数 nn 和 mm，nn 表示烽火台的数量，mm 表示山峰的数量。

接下来的 nn 行定义了烽火台的位置，每个烽火台的位置用一对整数 xx 和 yy 来表示。

接下来的 mm 行描述了所有的山峰，每个山峰用三个数来表示 x,y,rx, y, r：x,yx, y 为整数，定义了山峰的位置，rr 定义了半径。

输出格式

输出一个整数：为使所有烽火台点燃，骑手们必须传递的信息数量。

样例输入

6  3
1  8
5  4
7  7
9  2
16  6
17  10
4  7  2
6  3  1
12  6  3

样例输出

2

数据范围

  • 1≤n≤10001\le n\le 1000，0≤m≤10000\le m\le 1000；
  • 0≤x≤1040\le x\le 10^4，0≤y≤1040\le y\le 10^4；
  • 1≤r≤50001\le r\le 5000。

来源与许可

本题为 NCPC 2009 试题「Beacons」，题面与测试数据整理自 BZOJ 2233。

样例 1

输入

6  3
1  8
5  4
7  7
9  2
16  6
17  10
4  7  2
6  3  1
12  6  3

输出

2