sept.24 Hopping Rabbit

portkey

扫描线

把所有坑挪到 \(d\times d\) 的区域
扫描线找有没有空挡

第一步 挪
注意 \(x_1,y_1,x_2,y_2\) 有负数
可能全覆盖：比如 \(x_2-x_1>d\)

第二步 扫描
维护行最小值即可

最后发现我程序设计课基础不过关
deal(in,in,in,in)是从后往前执行的（逗号的顺序）

#include<bits/stdc++.h>
using namespace std;
#define in Read()
typedef pair<int,int> PII;

int in{
    int i=0,f=1; char ch=0;
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') f=-1, ch=getchar();
    while('0'<=ch&&ch<='9') i=(i<<1)+(i<<3)+ch-48, ch=getchar();
    return i*f;
}

const int N=1e5+5;
int n,d,ansx,ansy;
vector<PII> add[N],del[N];

struct TREE{
    int tag, val;
}tre[N<<2];

#define lch p<<1
#define rch p<<1|1
#define mid (l+r>>1)

void push_up(int p,int l,int r){
    tre[p].val=min(tre[lch].val,tre[rch].val);
}

void push_down(int p){
    tre[lch].tag+=tre[p].tag;
    tre[lch].val+=tre[p].tag;
    tre[rch].tag+=tre[p].tag;
    tre[rch].val+=tre[p].tag;
    tre[p].tag=0;
    return;
}

void build(int p,int l,int r){
    tre[p].tag=0;
    if(l==r){
        tre[p].val=0;
        return;
    }
    build(lch,l,mid);
    build(rch,mid+1,r);
    push_up(p,l,r);
    return;
}

void update(int p,int l,int r,int L,int R,int x){
    if(L<=l&&r<=R){
        tre[p].tag+=x;
        tre[p].val+=x;
        return;
    }
    push_down(p);
    if(mid>=R) update(lch,l,mid,L,R,x);
    else if(mid<L) update(rch,mid+1,r,L,R,x);
    else update(lch,l,mid,L,R,x), update(rch,mid+1,r,L,R,x);
    push_up(p,l,r);
    return;

}

int query(int p,int l,int r,int L,int R){
    if(L<=l&&r<=R) return tre[p].val;
    push_down(p);
    if(mid>=R) return query(lch,l,mid,L,R);
    if(mid<L) return query(rch,mid+1,r,L,R);
    return min(query(lch,l,mid,L,R),query(rch,mid+1,r,L,R));
}

#undef lch
#undef rch
#undef mid

void deal(int x1,int y1,int x2,int y2){
    int xl(0), xr(0), yl(0), yr(0);
    if(x2-x1>=d) xl=1, xr=d;
    else{
        xl=(x1%d+d)%d+1;
        xr=((x2-1)%d+d)%d+1;
    }

    if(y2-y1>=d) yl=1, yr=d;
    else{
        yl=(y1%d+d)%d+1;
        yr=((y2-1)%d+d)%d+1;
    }

    if(xl<=xr){
        if(yl<=yr){
            add[yl].push_back(make_pair(xl,xr));
            del[yr+1].push_back(make_pair(xl,xr));
        }else{
            add[yl].push_back(make_pair(xl,xr));
            del[d+1].push_back(make_pair(xl,xr));

            add[1].push_back(make_pair(xl,xr));
            del[yr+1].push_back(make_pair(xl,xr));
        }
    }else{
        if(yl<=yr){
            add[yl].push_back(make_pair(xl,d));
            del[yr+1].push_back(make_pair(xl,d));

            add[yl].push_back(make_pair(1,xr));
            del[yr+1].push_back(make_pair(1,xr));
        }else{
            add[yl].push_back(make_pair(xl,d));
            del[d+1].push_back(make_pair(xl,d));

            add[yl].push_back(make_pair(1,xr));
            del[d+1].push_back(make_pair(1,xr));

            add[1].push_back(make_pair(xl,d));
            del[yr+1].push_back(make_pair(xl,d));

            add[1].push_back(make_pair(1,xr));
            del[yr+1].push_back(make_pair(1,xr));
        }
    }
}

int main(){

    // freopen("1.in","r",stdin);

    n=in, d=in;
    for(int i=1;i<=n;++i){
        int a=in, b=in, c=in, d=in;
        deal(a,b,c,d);
    }

    build(1,1,d);

    for(int y=1;y<=d;++y){
        for(PII it:add[y]) update(1,1,d,it.first,it.second,1);
        for(PII it:del[y]) update(1,1,d,it.first,it.second,-1);
        if(query(1,1,d,1,d)==0){
            for(int x=1;x<=d;++x){
                if(query(1,1,d,x,x)==0){
                    ansx=x, ansy=y;
                    break;
                }
            }
            break;
        }
    }

    if(!ansx) puts("NO");
    else printf("YES\n%d %d\n",ansx-1+d,ansy-1+d);
    return 0;
    
}