OI题库

智破连环阵

【问题描述】

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个测试点的得分。