[NOI2003]智破连环阵
题号:NC16902
时间限制:C/C++/Rust/Pascal 6秒,其他语言12秒
空间限制:C/C++/Rust/Pascal 128 M,其他语言256 M
Special Judge, 64bit IO Format: %lld

题目描述

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应当尽量小。

输入描述:

第一行包含三个整数: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是随机生成的。

输出描述:

第一行包含一个整数x,表示实际使用的炸弹数。第二行包括x个整数,依次表示a1,a2,…,ax。
示例1

输入

复制
4 3 6
0 6
6 6
6 0
0 0
1 5
0 3
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

输出

复制
5
6 2 1 3 4