P1526 [NOI2003] Breaking the Linked Formation

After spending tens of billions, Country B finally developed a new weapon — the Linked Formation (Zenith Protected Linked Hybrid Zone). Legend says the Linked Formation is a self-sustaining intelligent weapon that never stalls. However, reconnaissance by Country A’s spies revealed that the Linked Formation actually consists of $M$ independent weapons numbered $1, 2, \ldots, M$. Initially, weapon $1$ is in the attack state, while all other weapons are in invincible defense. Thereafter, once weapon $i$ ($1 \leq i < M$) is destroyed, weapon $i+1$ automatically switches from invincible defense to the attack state $1$ second later. When weapon $M$ is destroyed, this expensive Linked Formation is destroyed. To thoroughly defeat Country B’s scientists, the defense minister of Country A plans to use the cheapest weapon — bombs — to destroy the Linked Formation. After long and precise probing, Country A’s scientists obtained the planar coordinates of the $M$ weapons in the Linked Formation, then determined the planar coordinates of $n$ bombs and planted them. Each bomb has a continuous detonation duration of $5$ minutes. During its activation window, each bomb can instantly eliminate any Country B weapon that is in the attack state and whose planar distance to it does not exceed $k$. Similar to the Linked Formation, bomb $a_1$ detonates continuously for $5$ minutes at first, then bomb $a_2$ detonates for $5$ minutes, then bomb $a_3$, and so on, until the Linked Formation is destroyed. Clearly, different sequences $a_1, a_2, a_3, \ldots$ have different effects. A good sequence may destroy the Linked Formation using only a small number of bombs; a bad sequence may fail even after using all bombs. Now, please determine an optimal sequence $a_1, a_2, a_3, \ldots$ such that the Linked Formation is destroyed during the detonation time of bomb $a_x$. Here, $x$ should be as small as possible.

The first line contains three integers: $M$, $n$, and $k$, denoting that the Linked Formation of Country B consists of $M$ weapons, Country A has $n$ bombs available, and the bomb attack radius is $k$. The next $M$ lines each contain a pair of integers $x_i, y_i$, representing the planar coordinates of weapon $i$. Then the next $n$ lines each contain a pair of integers $u_i, v_i$, representing the planar coordinates of bomb $i$. The input testdata is guaranteed to be random, correct, and to have a solution.

One line containing an integer $x$, the actual number of bombs used.

For $100\%$ of the testdata, $1 \leq M, n \leq 100$, $1 \leq k \leq 1000$, $0 \leq x_i, y_i \leq 10000$, $0 \leq u_i, v_i \leq 10000$. Each test point has a time limit of $2$ seconds. Translated by ChatGPT 5