Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Sofdor Ali and Attack Optimization

By Kryptonyte · Limits 2s, 512 MB

Tuki and Jha is in the middle of an interplanetary war and their base is under drone attack! They are helpless and asked for Sofdor Ali's help. Sofdor does not like wars and passed the situation to you.

There is a radar at origin O. The radar is able to identify N drone(s) around it's 360 degrees.

Origin and drone(s) are defined over a 2D Cartesian grid. Each drone has a velocity, the distance it can cover in one second of time towards the origin. If a drone comes within R distance of the origin, it can attack the origin and destroy it. We have the full fire power to eliminate all the drones together at a time. But the cost for such an attack is the highest Euclidean distance of a drone from the origin O. You need to minimize the cost of the attack such that no drone can attack the origin. If you can not avoid drone's attack, then just print "-1". As the attack is not automated ( you will have to perform the attack ), the origin can only attack the drones in integer unit of time. That is, the origin can attack the drones in the first, second, third or any integer amount of seconds, but not in any fractional amount of seconds. Being machines, drones do not care about integer time. They will attack as soon as they can.

You will also have to tell us different positions of the drones when it is optimal to attack the drones. Print them in the order of leftmost and lowermost points(in case of tie occurs in leftmost point).

Note: Input data represents the configuration ( position of the drones ) in the 0th second. You can attack from the 1st second.


Input starts with an integer T, denoting the number of test cases. Each case starts with two integers (X Y), coordinate of the origin. Second line starts with N which denotes number of drone(s). Next N lines denote the information of the drone(s). The i'th line contains three integer (DXi, DYi, Vi) which denotes the coordinate (DXi, DYi) and the velocity (Vi) of the i'th drone. Finally each case ends with R which is explained in the problem statement.

For around 6% input:

There will be only impossible cases.

1 ≤ T ≤ 5

For around 34% input:

The drone will be only on the axis( X and Y axis), visit only integer positions and velocity will be constant for N drones. and also origin O will be always at (0,0).

1 ≤ T ≤ 20

1 ≤ R ≤ 100

1 ≤ N ≤ 100

-100 ≤ DXi , DYi ≤ 100

0 ≤ Vi ≤ 100

For around 60% input

1 ≤ T ≤ 20

1 ≤ R ≤ 10000000

1 ≤ N ≤ 10000

-1000000000 ≤ DXi , DYi ≤ 1000000000

0 ≤ Vi ≤ 10000000


Print the cost of the attack. If it is not possible to avoid drone's attack then print -1. If it is possible to attack all the drones then provide the different positions of the drones in optimal configuration. Print the positions the way it was mentioned in the problem statement. The difference between your solution and judges solution must be less than 10-6.

See the sample output for details.


0 0
0 3 1
0 -3 1
3 0 1
-3 0 1
0 0
0 1 1
0 -1 1
1 0 1
-1 0 1
-1.000000000000000 0.000000000000000
0.000000000000000 -1.000000000000000
0.000000000000000 1.000000000000000
1.000000000000000 0.000000000000000


For the first test case, there are four drones at (0,3) , (0,-3) , (3,0) and (-3,0) each with velocity one unit/second. After 2 seconds they are at position (0,1) , (0,-1) , (1,0) and (-1,0) respectively and the optimal cost of attack is 1.