Problem S

One fateful spring evening Bergur was playing his favorite video game Striker-Count. Bergur is so good at Striker-Count he usually defeats his opponents without breaking a sweat. Therefore he’s been racking his brain for new ways to win with style. He decides to jump in the air, rotate a full circle and shoot one shot with his trusty PWA. But he’s been wondering, what is the maximum amount of opponents he can hit with one shot in this fashion.

We consider Bergur to positioned at the origin of a plane. His opponents are then provided as circles with a center somewhere in the plane and a radius. A single shot is then a ray from the origin and hits the opponent if and only if the ray intersects strictly more than one point of the opponent (i.e. grazing the opponent doesn’t count as a hit). It is guaranteed that no opponents include Bergur (the origin). Enemies might overlap however since they might be standing on top of one another. By sheer skill Bergur will still manage to hit both of them with a single shot if the ray intersects both circles.


The first line of the input contains an integer $1 \leq n \leq 10^5$, which denotes the number Bergur’s opponents present on the plane. Then $n$ lines follow, the $i$th of which contains three real numbers $-10^9 \leq x_ i, y_ i \leq 10^9$, $0 < r \leq 10^9$ which denote an opponent centered at point $(x_ i, y_ i)$ in the plane with radius $r_ i$. All real numbers will have at most six digits after the decimal point. It is guaranteed that there is a neighbourhood around an optimal angle of radius $10^{-9}$ such that all angles in the neighbourhood give the same number of hit enemies.


The only line of the output should contain the maximum number of opponents Bergur can hit with one shot.

Sample Input 1 Sample Output 1
5 0 1
10 0 1
0 5 1
0 -5 1
-5 0 1
Sample Input 2 Sample Output 2
2 2 2
6 2 1
10 2 1
2 6 1
6 6 1
2 10 1

Please log in to submit a solution to this problem

Log in