题解 P2928【[USACO09HOL]牛的打手】
题目要求求一个运动的点 在 一堆运动的点的多少个的一定范围内
那么我们可以先转换为一个运动的点的一定范围内有其他运动的点中的多少个（求最多的时刻的个数）
那么聪明的我们都学过物理
物体的运动是相对的 所以我们让那个要找范围的运动点不动 所以就成了相对的 相对位置减一下 相对速度也减一下所以这道题和牛绣有了异曲同工之妙
先算出交点 但是此时我们是以时间为未知量的 他不可能为负数吧！
（注意速度是有方向的）
然后我们可以推导三种情况
第一种 两端点都是正数
那么两个点的时间就是方程解得的时间
第二种 两端点都是负数
两个点都是反向延长线 答案此时不存在
第三种 两端点一正一负
此时点在那个圆的中间 所以两端点时间一个为0 另一个为所求得的正值
所以我们用计算几何先求出点 之后再用一次扫描线就可以得到答案啦！
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<queue>
#include<stack>
#include<cmath>
#define LL long long
using namespace std;
struct node{
int num;
double v;
}e[100100];
int v[100100];
double r,bx,by,bvx,bvy;
int n,cnt;
double x,y,vx,vy;
inline int cmp(node a,node b)
{
return a.v < b.v;
}
int main()
{
scanf("%d%lf%lf%lf%lf%lf",&n,&r,&bx,&by,&bvx,&bvy);
//敌动我动还能算吗？
//考虑位移是相对的 把速度改一下 位置也改一下
for(int i=1;i<=n;i++)
{
scanf("%lf%lf%lf%lf",&x,&y,&vx,&vy);
x-=bx;//3
y-=by; //1
vx-=bvx;//3
vy-=bvy;//1
// X= x + t*vx
// Y= y + t*vy
// X*X+Y*Y=r*r
if(vx==0 && vy==0)
{
if(x*x+y*y<=r*r)
{
e[++cnt].v = 0;
e[cnt].num = i;
}
continue;
}
// x*x + vx*vx*t*t + 2*x*vx*t +
// y*y + vy*vy*t*t + 2*y*vy*t = r*r
// (vx*vx+vy*vy)*t*t+ (2*x*vx+2*y*vy)*t + x*x+y*y-r*r =0
double A=vx*vx+vy*vy;
double B=2*x*vx+2*y*vy;
double C=x*x+y*y-r*r;
double delta=B*B-4*A*C;
// cout<<x<<" "<<y<<" "<<vx<<" "<<vy<<" "<<A<<" "<<B<<" "<<C<<" "<<delta<<" YYYY "<<endl;
if(A<=1e-8)
{
if(C>0) continue;
e[++cnt].v = 0;
e[cnt].num = i;
e[++cnt].v = 1e9;
e[cnt].num = i;
continue;
}
else if(delta<0) continue;
else
{
if((-B-sqrt(delta))*1.0/(2*A)<0 && (-B+sqrt(delta))*1.0/(2*A)<0) continue;
e[++cnt].v = (-B-sqrt(delta))*1.0/(2*A);
e[cnt].num = i;
e[++cnt].v = (-B+sqrt(delta))*1.0/(2*A);
e[cnt].num = i;
}
}
sort(e+1,e+1+cnt,cmp);
LL ans=0,tmp=0;
for(int i=1;i<=cnt;i++)
{
// cout<<e[i].num <<" "<<e[i].v<<" TYTYTYT "<<endl;
int num=e[i].num;
if(v[num]==0)
{
tmp++;
v[num]=1;
}
else
{
tmp--;
}
if(tmp>ans) ans=tmp;
}
printf("%lld",ans);
}