#1605. [Ncpc2009]Beacons
[Ncpc2009]Beacons
Background
Special for beginners, ^_^
Description
在远古时代,信息的交流没有我们现在这么便利。一个国家在战争时期,可能花好几个月的时间来集合军队。但是在作战区用上烽火台,就有可能快速地传递军事信号。
当第一个烽火台被点燃,所有能看到这个烽火台的其他烽火台也将被点燃,所有能看到这些烽火台的其他烽火台也将被点燃,如此继续直到所有烽火台都被点燃---自然所有的烽火台都在彼此的视野范围内,直接地或间接地。如果不是这样,则紧急的信息必须由骑手们在一些烽火台间传递。
给出这个国家所有烽火台的位置,同时还给出山峰的位置和大小,写一个程序来决定多少信息要被骑手们传递,使得在敌人入侵这个国家时,所有的烽火台都要被点燃。
简单来说,我们这样来定义一个国家的模型:一个烽火台就用XY平面上的一个点来表示,一座山峰就用一个圆来表示。如果两个烽火台的连接直线上没有山峰座落,则认为这两个烽火台是在相互的视野内。
输入是这样构造的:任何一对烽火台的连线不会与山峰的圆周相切,除非这个连接线通过了别的山峰的内部。山峰不会重叠或相切,任何一个烽火台也不会在山峰内或它的圆周上。
Format
Input
第一行有两个整数n (1<=n <=1000) and m (0 <=m <=1000),n表示烽火台的数量,M表示山峰的数量。接下来的N行定义了烽火台的位置。每个烽火台的位置用一对整数X和Y来表示(0 <= x; y <= 10000).接下来的M行描述了所有的山峰。每个山峰用三个数来表示:X Y R. X Y为整数(0 <= x; y <= 10000)定义了山峰的位置,R定义了半径(1 <= r <= 5000)
Output
输出一个整数:为使所有烽火台点燃,骑手们必须传递的信息数量
Samples
6 3
1 8
5 4
7 7
9 2
16 6
17 10
4 7 2
6 3 1
12 6 3
2
Limitation
1s, 1024KiB for each test case.