题解 P3122 【[USACO15FEB]圈住牛Fencing the Herd】

BJpers2 · 2019-03-06 16:35:38 · 题解

一道很好的计算几何题，结合了CDQ分治的思想，而且也不需要很毒瘤的前置知识（比如三维凸包，半平面交之类）。

为了表述方便，我们强制令B \geq 0

首先根据套路，遇到这种“只有插入，动态询问”的题目，往往可以往CDQ分治上面去想。

一个栅栏是有用的，当且仅当把它之前的所有点带入Ax+By-C中去计算，所得值的符号全部相同。又等价于最大，最小值同号。最大值在”以它为斜率的直线在上凸包上的切点”处取到(因为B \geq 0),特别地，当B=0,在凸包最右端取到。而最小值则相反。

下面只考虑在一次分治中如何转移最大值。

构建上凸包。
对所有直线按照斜率递减排序，竖线强制放在最后，实现上可以把每条非竖直线赋一个指向x轴正方向的方向向量，按后面\times前面\leq 0为基准排序,并令竖线方向指向下，就可以不用特判竖线了。
此后类似于旋转卡壳，将斜率在(slope(i-1,i),slope(i,i+1)]中的所有直线的答案更新，在凸包两端的情况特殊注意。

最小值同理，注意几乎所有符号都要取反，且竖线要放左边。

最后判同号时千万别偷懒写mx[i] \times mi[i]>0 ,这样做稳爆long long,我就因为这拍了半天一直没拍出来，写成mx[i]<0 || mi[i]>0就好了

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
typedef long long ll;
const int N=200200,M=200200;
const ll INF=4e18;
int n,m,cp,cl,r;
ll mx[M],mi[M];
struct vec{
    ll  x,y;
    vec(){}
    vec(ll  a,ll  b){x=a;y=b;}
    vec operator + (vec a){return vec(x+a.x,y+a.y);} 
    vec operator - (vec a){return vec(x-a.x,y-a.y);}
    ll  operator ^ (vec a){return x*a.y-y*a.x;} 
}p[N],h[N],di[M];
struct lin{vec d;int i;}L[M];
struct qry{int o;ll x,y,z;}q[M];
void upd(int i,ll x,ll y){
    ll va=x*q[i].x+y*q[i].y;
    mx[i]=max(mx[i],va);
    mi[i]=min(mi[i],va);
}
bool cmp(vec a,vec b){return a.x==b.x?a.y<b.y:a.x<b.x;}
bool cmp1(lin a,lin b){return (a.d^b.d)>0;}
bool cmp2(lin a,lin b){return (a.d^b.d)<0;}
void sol(int l,int r){
    if(l==r) return;
    int md=(l+r)>>1;
    sol(l,md),sol(md+1,r);cp=cl=0;
    FOR(i,l,  md) if(q[i].o==1) p[++cp]=vec(q[i].x,q[i].y);
    FOR(i,md+1,r) if(q[i].o==2) L[++cl]=(lin){di[i],i};
    if(!(cp*cl)) return; 
    sort(p+1,p+cp+1,cmp);
    h[r=1]=p[1];
    FOR(i,2,cp){
        while(1<r && ((h[r]-h[r-1])^(p[i]-h[r]))<=0) r--;
        h[++r]=p[i];
    } 
    sort(L+1,L+cl+1,cmp1);
    int j=1;
    FOR(i,1,r){
        for(;(i+1>r || (L[j].d^(h[i+1]-h[i]))>=0) && j<=cl;j++) 
            upd(L[j].i,h[i].x,h[i].y);
    }//下凸包 

    h[r=1]=p[1];
    FOR(i,2,cp){
        while(1<r && ((h[r]-h[r-1])^(p[i]-h[r]))>=0) r--;
        h[++r]=p[i];
    } 
    sort(L+1,L+cl+1,cmp2);
    j=1;
    FOR(i,1,r){
        for(;(i+1>r || (L[j].d^(h[i+1]-h[i]))<=0) && j<=cl;j++) 
            upd(L[j].i,h[i].x,h[i].y);
    }//上凸包 
} 
int main(){
    scanf("%d%d",&n,&m);m+=n;
    FOR(i,1,n) q[i].o=1,scanf("%lld%lld",&q[i].x,&q[i].y);
    FOR(i,n+1,m){
        scanf("%d",&q[i].o);
        if(q[i].o==1) scanf("%lld%lld",&q[i].x,&q[i].y);
        if(q[i].o==2){
            scanf("%lld%lld%lld",&q[i].x,&q[i].y,&q[i].z);
            if(q[i].y<0) q[i].x*=-1,q[i].y*=-1,q[i].z*=-1; 
            if(q[i].y==0 && q[i].x<0) q[i].x*=-1,q[i].z*=-1;
            di[i]=vec(q[i].y,-q[i].x); 
            mx[i]=-INF;mi[i]=INF;
        }
    }
    sol(1,m);
    FOR(i,n+1,m)if(q[i].o==2) 
        mx[i]-q[i].z<0 || mi[i]-q[i].z>0?puts("YES"):puts("NO");
}