405596: GYM102006 I Rise of the Robots

You made a robot to compete in an international competition. The organizers require that each robot must complete a set of movements to test its reflexes and balance before the competition starts.

A robot will make n moves on a circular table of radius R centered at (0, 0), each move is in a straight line. For the i^th move, the robot will move from its current location (x, y) to (x + dx_i, y + dy_i).

Everything is set for your test run, but you are faced with one final problem; you realized that your robot is out of balance. If any part of it gets off the table, it will fall and you will lose the competition. Your robot will be represented as a circle with radius r, with its location being the center of the circle.

Can you figure out a possible starting location for the robot to complete all the movements without falling?

The first line of input contains an integer T, the number of test cases.

The first line of each test case contains three integers, n, R and r (1 ≤ n ≤ 250, 1 ≤ r < R ≤ 10⁵), the number of moves, the radius of the table, and the radius of the robot.

The i^th of the following n lines contains two integers dx_i and dy_i (|dx_i| + |dy_i| > 0), representing the i^th move.

It is guaranteed that there is at least one valid starting position to place the robot on.

For each test case, output two numbers (S_x, S_y) on a single line, the coordinates of a valid starting position.

Your answer is considered correct if by extending the radius of the table R by 10^- 4, the robot will be strictly inside the table throughout all moves.

1
4 5 2
3 0
0 3
3 -3
-3 -3

-3.000000000 0.000000000