National Olympiad in Informatics, China, 2003

Day 2, Problem 3 - ZPLHZ

After spending ten billion dollars, country B has developed a new weapon - the Zenith Protected Linked Hybrid Zone (ZPLHZ). According to legend, the ZPLHZ is a type of spontaneously acting, intelligent weapon that is running nonstop. However, a spy from country A has discovered that the ZPLHZ actually consists of M independent weapons labeled from 1 to M. Each weapon has two types of statuses: invincible defense mode and attack mode. Initially, weapon number 1 is used for attack, and all other weapons are set to invincible defense mode. Afterwards, if at any time the i-th (1 ≤ i < M) independent weapon is destroyed, then 1 second after, the (i+1)-th weapon will automatically change from invincible defense mode to attack mode. When the M-th weapon is destroyed, this incredibly expensive ZPLHZ weapon will be entirely destroyed.

To defeat country B, the commander of country A's military decides to use one of the cheapest weapons - bombs, to destroy the ZPLHZ. After a long period of sophisticated research and top-secret spying, country A's military strategists managed to acquire 2D coordinates of the M weapons that make up the ZPLHZ. Based on these, they have selected n points on which to plant special time bombs. These n points are labeled from 1 to n. Each bomb has a radius of k, and will continuously detonate for 5 minutes. Within these 5 minutes, each bomb can instantly destroy all the attack mode weapons from country B that is within a straight-line distance of no larger than k from the bomb. Similar to the ZPLHZ, bomb a₁ will detonate for 5 minutes, then bomb a₂ will detonate for 5 minutes, followed by bomb a₃, and so forth until the ZPLHZ is destroyed. At the time of each detonation, the undetonated bombs at that time are buried underground, and thus will not be destroyed.

Clearly, it is vital to select the right values for a₁, a₂, a₃, … A good program can use the minimal number of bombs while also fully destroying the ZPLHZ. A bad program may use up all the bombs and still not destroy the ZPLHZ. Now, you must determine a sequence a₁, a₂, a₃, … so that during the detonation period of bomb a_x, the ZPLHZ will be destroyed. Here, the value of x must be as small as possible.

Input Format

The first line of input will contain one integer T, the number of test cases to follow. For each test case:

• The first line contains three integers M, n, and k (1 ≤ M, n ≤ 100, 1 ≤ k ≤ 1000), indicating that country B's ZPLHZ consists of M independent weapons, country A has n bombs at their disposal, and the radius of each bomb is k.
• The next M lines each contains a pair of integers x_i and y_i (0 ≤ x_i, y_i ≤ 10000), describing the 2D coordinates of the i-th weapon.
• The next n lines each contains a pair of integers u_i and v_i (0 ≤ x_i, y_i ≤ 10000), describing the 2D coordinates of i-th (1 ≤ i ≤ n) bomb.

It is guaranteed that the input will always be valid and will always have a solution.

Output Format

For each test case, there should be two lines:

• The first line should contain the integer x, representing the number of bombs used.
• The second line should contain x integers, the values of a₁, a₂, …, a_x.

Sample Input

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

Sample Output

2
1 3
5
6 2 1 3 4

Scoring

For each test case, if your output is valid, then you will be scored as follows.

where good is our official solution for x, and ans is your solution. If your output is illegal, then your score for the test case will be 0.

Each test case is scored out of 10, and your total score will be the sum of your scores on each test case. However, a submission cannot score more than 100% of the points.

All Submissions
Best Solutions

Point Value: 25 (partial)
Time Limit: 2.00s
Memory Limit: 64M
Added: May 18, 2014

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)