Interstellar Travel

This problem was used in the following GFU competitions:

• GFU 2024 D1 Q12

You are planning to travel in interstellar space in the hope of finding habitable planets. You have already identified N stars that can recharge your spaceship via its solar panels. The only work left is to decide the orientation of the spaceship that maximizes the distance it can travel.

Space is modeled as a 2D plane, with the Earth at the origin. The spaceship can be launched from the Earth in a straight line, in any direction. Star i can provide enough energy to travel Ti distance if the spaceship is launched at an angle of ai with the x-axis. If the angle is not perfectly aligned, then the spaceship gets less energy. Specifically, if the launch direction makes an angle of a with the x-axis, then it gets enough energy to travel distance of 

max(0, Ti - si × dist(ai; a))

from star i, where dist(a,b) is the minimum radians needed to go from angle a to b. The distance that the spaceship can travel is simply the sum of the distances that each star contributes. Find the maximum distance T that the starship can travel.

The first line will contain a single integer x that indicates the number of test cases that follow. Each test cases will begin with a single integer N, 1 <= N <= 105. Following this are N inputs each containing three real numbers Ti, si, and ai, with 0 < Ti <= 1000, 0 <= si <= 100, and 0 <= ai < 2p . All real numbers in the input have at most 6 digits after the decimal point.

Output, for each test case on a single line, the maximum distance the spacecraft can travel. Format your answers as shown in the example output. Your answer is considered correct if it has an absolute

or relative error of at most 10^-6.