BZOJ 1580
直接解析算出每段的时间然后模拟即可
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <cmath>
#define Pa pair<double,double>
#define mp make_pair
#define pb push_back
#define se second
#define fi first using namespace std;
const int Maxn=;
const int Inf=0x3f3f3f3f;
int n,R,X,Y,Vx,Vy,P[Maxn],Q[Maxn],Vp[Maxn],Vq[Maxn],Ans;
vector<Pa> V;
inline int Sqr(int x) {return x*x;}
inline double Max(double x,double y) {return x>y?x:y;}
int main()
{
// freopen("c.in","r",stdin);
scanf("%d%d%d%d%d%d",&n,&R,&X,&Y,&Vx,&Vy);
for (int i=;i<=n;i++)
{
scanf("%d%d%d%d",&P[i],&Q[i],&Vp[i],&Vq[i]);
P[i]-=X,Q[i]-=Y,Vp[i]-=Vx,Vq[i]-=Vy;
}
for (int i=;i<=n;i++)
if (Vp[i]== && Vq[i]==)
{
if (Sqr(P[i])+Sqr(Q[i])<=Sqr(R))
V.pb(mp(,Inf));
} else
{
double Dis=-(P[i]*Vp[i]+Q[i]*Vq[i])/sqrt((Sqr(Vp[i])+Sqr(Vq[i])));
if (R*R>=(double)Sqr(P[i])+(double)Sqr(Q[i])-Dis*Dis)
{
double tmp=sqrt(R*R-Sqr(P[i])-Sqr(Q[i])+Dis*Dis);
V.pb(mp(Max(Dis-tmp,0.0)/sqrt(Sqr(Vp[i])+Sqr(Vq[i])),(Dis+tmp)/sqrt(Sqr(Vp[i])+Sqr(Vq[i]))));
}
} sort(V.begin(),V.end());
priority_queue<double> T; for (int i=;i<V.size();i++)
{
T.push(-V[i].se);
while (!T.empty() && -T.top()<V[i].fi) T.pop();
Ans=Max(Ans,T.size());
}
printf("%d\n",Ans);
return ;
}
BZOJ 1580