Janeway`s Journey#6970
Captain Janeway wants to take the Voyager through an asteroid field, but there are too many asteroids for such a trip to be safe. To help blaze a path, you have been asked to take a shuttle into the asteroid field. Your plan is to fly through the field and note its layout, then position the shuttle in such a manner to take out as many asteroids as possible with a single, straight-line phaser blast.
For simplicity we will model this problem in the plane, with circular asteroids, an infinitely thin phaser, and the ability to position your shuttle wherever and however you like, in or around the asteroid field.
Starts with a line that contains the number of test cases (1 \leq t \leq 25). Each test case begins with a line with a single integer (1 \leq n \leq 2000) denoting the number of asteroids. Furthermore, there will be at most test cases for which n > 500. This line is followed by lines each with space-separated real numbers x_i, y_i, r_i which specify that asteroid is centered at (x_i, y_i) and has radius r_i (-10^{6} \leq x_i, y_i \leq 10^6, 1 \leq r_i \leq 100). All of these numbers will be given to two decimal places. No asteroids will overlap or intersect each other. The input will be such that the answer will not change even if the radii of the asteroids vary by 10^{-6} in either direction.
For each test case, print a single integer on its own line denoting the maximum number of asteroids that may be destroyed.
Esempio 1