G |
Underwater
Snipers Input: Standard Input Output: Standard Output |
King Motashota is in a
war against the mighty Bachchaloks. He has formed a well-trained army of
snipers, and planning to use them as much as possible. In one of the missions,
he has S snipers. They will be dispatched to get rid of the
soldiers guarding the bank of the river 'Nodi'.
From satellite images, Motashota
has located positions of all enemy soldiers. Now, the plan is, snipers will
take their positions. They are excellent swimmers, so, you can assume that they
won't get caught, while taking position. Upon order from Motashota, they
will start shooting enemy soldiers. A sniper can shoot a soldier, if euclidean
distance between the soldier and sniper is no more than D. After
the snipers get rid of all the soldiers, they can proceed with the operation.
So, it is important for them to position the snipers in such a way that, all
soldiers are within the range of at least one sniper.
In addition, when snipers start
shooting, the guards will be alert, and thus, snipers can't change their
position, they can only continue shooting from their position.
The river bank is defined by the
horizontal line y = k. All points (x,y) where y>k
is in the enemy territory, and if y<k, then it's on the water. You
will be given location of N soldiers, strictly in the enemy
territory, you have to place S soldiers in the water, so that,
they can kill all soldiers. For security reasons, the snipers should be as far
from the bank as possible. For any sniper in position (xi,yi),
the distance from the bank is |yi-k|. If, for all
snipers, the minimum of them is M=min{|yi-k|}, you have
to maximize M.
Both the soldiers and snipers
are really superstitious. They will stay only in integer coordinates.
Input
First line contains an integer T(1≤T≤100),
the number of test cases.
This is followed by T
test cases. Each test case starts with four integers, k(-108≤k≤108), N(1≤N≤10000),
S(1≤S≤10000) and D(1≤D≤109),
the position of the bank, number of guards and number of snipers, and the range
of the snipers.
This is followed by N
lines, each containing a pair of integers (xi, yi)
the position of ith guard (-108 ≤ xi
≤ 108, k < yi ≤ 108).
There is a blank line before each test case.
Output
For each test case, output the
case number followed by an integer, M, which is defined in the
statement. If the snipers can’t kill all guards, output: “IMPOSSIBLE”.
2 0 3 2 4 1 1 3 2 9 1 0 3 1 4 1 1 3 2 9 1 |
Case 1: 2 Case 2: IMPOSSIBLE |
Problemsetter: Manzurur Rahman
Khan, Special Thanks: Jane Alam Jan, D. Kisman