题解 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);
}