[线段树][数学][离散化]luogu P2928 牛的打手

小鱼儿 2021-12-16 01:11 230阅读 0赞

https://www.luogu.org/problemnew/show/P2928

# 分析 #

一道挺有意思的思维题

因为所有点都在运动，不好做，我们把运动改为相对的

设bessie在原点(0,0)，不运动，则杀手们的参数则为(x-bx,y-by,vx-vbx,vy-vby)

那么题目就变为求杀手什么时候进入或相切以r为半径原点为圆心的圆

可以有方程：

$r^2=(x+tvx)^2+(y+tvy)^2$

化为常规式

$(vx^2+vy^2)t^2+2\*(x\\cdot vx+y\\cdot vy)t+x^2+y^2-r^2=0$

然后解出方程，将两个解存进数组里，排序离散化

拿个线段树来累计答案即可

注意：

1、如果有在相对运动中不运动的点，要判断是否一直在圆内或上  
2、要判无解，解小于0等情况

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    typedef double db;
    const int N=5e4+10;
    struct Cow {
        db x,y,vx,vy;
        void In() {scanf("%lf%lf%lf%lf",&x,&y,&vx,&vy);}
        Cow operator - (Cow &b) {
            return (Cow){x-b.x,y-b.y,vx-b.vx,vy-b.vy};
        }
    }t,a[N];
    int s[N<<3],lz[N<<3],rt=1;
    int cnt;
    db p[2*N],q[N][2];
    int n,r,ans,e;
    
    void Calc(int x) {
        db A=pow(a[x].vx,2)+pow(a[x].vy,2),B=2*a[x].x*a[x].vx+2*a[x].y*a[x].vy,
        C=pow(a[x].x,2)+pow(a[x].y,2)-pow(r,2);
        db delta=pow(B,2)-4.0*A*C;
        if (delta<0.0) return;
        db d_root=sqrt(delta);
        db x1=(-1.0*B-d_root)/(2.0*A),x2=(-1.0*B+d_root)/(2.0*A);
        if (x1<0.0) x1=0;if (x2<=0.0) return;
        p[++cnt]=x1,1;p[++cnt]=x2,-1;
        q[cnt>>1][0]=x1;q[cnt>>1][1]=x2;
    }
    
    void Pushdown(int x) {
        s[x<<1]+=lz[x];lz[x<<1]+=lz[x];
        s[(x<<1)+1]+=lz[x];lz[(x<<1)+1]+=lz[x];
        lz[x]=0;
    }
    
    void Add(int x,int l,int r,int L,int R) {
        if (r<L||R<l||r<l) return;
        if (L<=l&&r<=R) {
            s[x]++;lz[x]++;
            return;
        }
        Pushdown(x);
        int mid=l+r>>1;
        if (L<=mid) Add(x<<1,l,mid,L,R);
        if (mid<R) Add((x<<1)+1,mid+1,r,L,R);
        s[x]=max(s[x<<1],s[(x<<1)+1]);
    }
    
    int main() {
        scanf("%d%d",&n,&r);
        t.In();
        for (int i=1;i<=n;i++) a[i].In(),a[i]=a[i]-t;
        for (int i=1;i<=n;i++)
            if (a[i].vx!=0||a[i].vy!=0) Calc(i);
                else if (pow(a[i].x,2)+pow(a[i].y,2)<=pow(r,2)) e++;
        sort(p+1,p+cnt+1);
        for (int i=1;i<=(cnt>>1);i++) {
            int l=lower_bound(p+1,p+cnt+1,q[i][0])-p,r=lower_bound(p+1,p+cnt+1,q[i][1])-p;
            Add(rt,1,cnt,l,r);
        }
        ans=s[rt]+e;
        printf("%d",ans);
    }

转载于:https://www.cnblogs.com/mastervan/p/11123382.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211215/bf850894ccbc4ab3b2fe554a09d3bf54.png