[Ncpc2009]Beacons

时间限制:10s      空间限制:256MB

题目描述

  

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

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

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

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

输入是这样构造的:任何一对烽火台的连线不会与山峰的圆周相切,除非这个连接线通过了别的山峰的内部。山峰不会重叠或相切,任何一个烽火台也不会在山峰内或它的圆周上。


输入格式

第一行有两个整数n (1<=n <=1000) and m (0 <=m <=1000),n表示烽火台的数量,M表示山峰的数量。接下来的N行定义了烽火台的位置。每个烽火台的位置用一对整数XY来表示(0 <= x; y <= 10000).接下来的M行描述了所有的山峰。每个山峰用三个数来表示:X Y R. X Y为整数(0 <= x; y <= 10000)定义了山峰的位置,R定义了半径(1 <= r <= 5000)


输出格式

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


样例输入

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

样例输出

2

提示

没有写明提示


题目来源

没有写明来源

Menuappsclose