Description
程序员不能总是整天坐着编程。有时站起来离开办公桌，休息一下，与同事闲聊，甚至玩一会，也是十分好的主意。F 公司的程序员就特别喜欢一种球类游戏。
让我们想象一个在笛卡尔坐标系平面上玩的游戏。玩家坐落在点 \((0,0)\) 上，选择任意一个方向，扔出球。飞了一会儿的球在距离原点 \(d\) 的地方撞击了平面，然后按照原来的方向继续飞。在第一次撞击之后，它继续飞且在距离原点 \(2d\) 的地方第二次撞击平面，接着诸如此类（按照选定的方向继续飞行，并且每隔 \(d\) 单位距离撞击一次平面）。因为在 F 公司的所有程序员都非常强壮，所以球可以飞到无穷远处。
平面上画有 \(n\) 个圆。如果球撞击平面且撞在一个画在平面上的圆内（包括边界），那么玩家得一分。球可以一次击中多个圆，并且对于它们每一个得一分（如果球在移动过程中一共撞击了某一个圆 \(x\) 次，那么玩家从中能得到 \(x\) 分）。
计算玩家向任意方向扔一个球所能得到的最大分数。注意可能有实数坐标。
\(1\le n\le 2\times 10^4,5\le d\le 10,-10^4\le x_i,y_i\le 10^4,1\le r_i\le 50\)。
Solution
有一个自然且正确的想法就是求出半径为 \(kd\) 的同心圆与给的圆的交点，然后排序。由于答案只会在交点处修改，那么就类似扫描线的扫一遍就可以了。
这个想法可以稍微优化一下。我们不求交点，求角度。因为 C++ 内置了三角和反三角函数。我们可以用 atan2 求出方位角，再用 acos 和余弦定理求出偏转的角度，注意处理一下超过 \(2\pi\) 的角。接下来就是基础的扫描线操作。
Code
#include<cmath>
#include<cstdio>
#include<algorithm>
#define N 20005
#define pi 3.1415926
#define eps 1e-8
#define db double
using namespace std;
int n,d,num,ans,res;
db l[N*20],r[N*20];
struct circ{db x,y,r;}a[N];
int main()
{
scanf("%d%d",&n,&d);
for (int i=1;i<=n;++i)
scanf("%lf%lf%lf",&a[i].x,&a[i].y,&a[i].r);
for (int i=1;i<=n;++i)
{
db dis=sqrt(a[i].x*a[i].x+a[i].y*a[i].y);
int st=ceil((dis-a[i].r)/d),ed=floor((dis+a[i].r)/d);
db theta=atan2(a[i].y,a[i].x);
if (theta<0) theta+=2*pi;
for (int j=st;j<=ed;++j)
{
int x=d*j;
db tta=acos((dis*dis+x*x-a[i].r*a[i].r)/(2*dis*x));
db t1=theta-tta,t2=theta+tta;
if (t2>=2*pi) t2-=2*pi,res++;
l[++num]=t1;r[num]=t2;
}
}
sort(l+1,l+num+1);sort(r+1,r+num+1);
ans=res;
for (int i=1,j=1;i<=num;)
{
db now=l[i];
for (;i<=num&&abs(l[i]-now)<eps;++i) ++res;
for (;j<=num&&r[j]<now;++j) --res;
if (res>ans) ans=res;
}
printf("%d\n",ans);
return 0;
}