[NOI2003]智破连环阵

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 关闭时间 2013年02月28日 星期四 23:02
输入文件 zplhz.in 输出文件 zplhz.out



智破连环阵

【问题描述】

B国在耗资百亿元之后终于研制出了新式武器——连环阵(Zenith Protected

Linked Hybrid Zone),并声称这是一种无敌的自发性智能武器。但A国经侦察发现,连环阵其实是由M个独立武器组成的。这M个武器编号为1,2,…,M。每件武器有两种状态:无敌自卫状态和攻击状态。最初,1号武器处于攻击状态,其他武器都处在无敌自卫状态。以后,一旦第i(1 <= i<M)号武器被消灭,1秒钟以后第i+1号武器就自动从无敌自卫状态变成攻击状态。当第M号武器被消灭以后,这个造价昂贵的连环阵就被彻底摧毁了。

为了打败B国,A国军事部长打算用最廉价的武器——炸弹来消灭连环阵。经过长时间的精密探测,A国的军事家们掌握了连环阵中M个武器的平面坐标,然后依此选择了n个点,并在这些点上安放了特殊的定时炸弹。这n个炸弹编号为1,2,…,n。每个炸弹的作用半径均为k,且会持续爆炸5分钟。在这5分钟内,每枚炸弹都可以在瞬间消灭离它直线距离不超过k的、处在攻击状态的B国武器。和连环阵类似,最初a1号炸弹持续引爆5分钟时间,然后a2号炸弹持续引爆5分钟时间,接着a3号炸弹引爆……以此类推,直到连环阵被摧毁。在每个炸弹爆炸的时候,其它尚未引爆的炸弹都处于地下隐蔽处,不会被己方的炸弹摧毁。

显然,选好a1、a2、a3...十分重要。好的序列可以在仅使用较少炸弹的情况下就能将连环阵摧毁;坏的序列可能在使用完所有炸弹后仍无法将连环阵摧毁。现在,请你决定一个序列a1、a2、a3…使得在第ax号炸弹引爆的时间内连环阵被摧毁。这里的x应当尽量小。

【输入文件】

输入文件zplhz.in第一行包含三个整数:M、n和k(1 <= M, n<= 100,1<= k<= 1000),分别表示B国连环阵由M个武器组成,A国有n个炸弹可以使用,炸弹攻击范围为k。以下M行,每行由一对整数xi,yi(0<= xi,yi <= 10000)组成,表示第i(1<= i<= M)号武器的平面坐标。再接下来n行,每行由一对整数ui,vi(0 <= ui,vi<= 10000)组成,表示第i(1<= i<= n)号炸弹的平面坐标。输入数据保证无误和有解。

测试数据中的xi、yi、ui、vi是随机生成的。

【输出文件】

输出文件zplhz.out的第一行包含一个整数x,表示实际使用的炸弹数。第二行包括x个整数,依次表示a1,a2,…,ax。

【样例输入1】

4 3 6

0 6

6 6

6 0

0 0

1 5

0 3

1 1

【样例输出1】

2

1 3

【样例输入2】

10 10 45

41 67

34 0

69 24

78 58

62 64

5 45

81 27

61 91

95 42

27 36

91 4

2 53

92 82

21 16

18 95

47 26

71 38

69 12

67 99

35 94

【样例输出2】

5

6 2 1 3 4

【评分标准】

对每个测试点,如果你的输出合法,评分公式如下:

其中good为我们的参考解,ans为你的答案。

如果你的输出不合法,则该测试点只能得0分。

总分的计算公式:

        

其中scorei为你第i个测试点的得分。