Codah ClubTrain. Submit. Improve.
Sign in
English
#000168

z-balloons

Little Z saved all this balloons from his birthday party, and he put some weird chemical on them so that when two balloons touch each-other they explode.

Little Z has N balloons, and he put them in his courtyard. Each balloon has the position of its center in the 3D coordinate plane, given with x, y, z. Also, each balloon is inflating with some speed, so that its radius in creasing V units each second. At the beginning the balloons are very small (a point in space)

You know the position x,y,z and the inflating speed of each of the N balloons. You know that two balloons explode if they touch each-other. If at the same moment more than two balloons touch each-other, they all explode.

You want to know which is the balloon that will survive, and will inflate to infinity.


InputFrom the first line of the standard input read an integer N (1 <= N <= 2000). From each of the next N lines read 4 integers x,y,z,V, representing the position and the increasing rate of the radius of the corresponding balloon. The values for x,y,z,V will all be in the range [0, 2000000000], with V >= 1

OutputTo the standard output write the index if the balloon that will survive, the indices are 0-based (the index of the last balloon is N-1). If none of the balloons survive, write -1

Input:
3
0 0 0 1
1 1 1 1
3 3 3 1
Output:
2
Explanation: At some moment balloons 0 and 1 will touch and explode, so the balloon 2 will survive

Input:
4
0 0 0 1
1 1 1 1
2 2 2 1
4 4 4 1
Output:
3
Explanation: At some moment balloons 0, 1 and 2 will touch (all at the same time) and explode, so the balloon 3 will survive

Input:
4
0 0 0 2
0 1 1 2
0 0 1 2
0 1 0 2
Output:
-1
Explanation: At some moment all the four balloons will touch (exact same moment) and they will all explode, so there is no survivor.

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.