-
题意:在二维平面上,分布着很多矩阵,这些矩阵是陷阱,有一只兔子每次固定向四周四个方向跳\(d\)个单位,问你是否存在一个起点,使得兔子无论怎么跳都不跳到陷阱中。
-
题解:因为兔子固定跳\(d\)个单位,因此具有周期性,也就是说,假如它的起点是\(d\)x\(d\)的矩阵的某一点,那么它无论跳到什么位置,该位置都能和初始矩形平移\(d\)个单位的起点重合.因此对于所有陷阱,我们可以将它们移到\(d\)x\(d\)的矩阵内,然后判断这个矩阵中有没有空的单位即可.问题进而转换成求矩形的面积并,然后就是一个裸的扫描线了。
-
代码:
#include <bits/stdc++.h> #define ll long long #define fi first #define se second #define pb push_back #define me memset #define rep(a,b,c) for(int a=b;a<=c;++a) #define per(a,b,c) for(int a=b;a>=c;--a) const int N = 1e6 + 10; const int mod = 1e9 + 7; const int INF = 0x3f3f3f3f; using namespace std; typedef pair<int,int> PII; typedef pair<ll,ll> PLL; ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;} ll lcm(ll a,ll b) {return a/gcd(a,b)*b;} int n,d; struct Segment{ ll y1,y2; int k; }; vector<Segment> seg[N]; struct Node{ ll l,r; ll cnt; ll len; }tr[N<<4]; void add(int x1,int y1,int x2,int y2){ seg[x1].pb({y1,y2,1}); seg[x2+1].pb({y1,y2,-1}); } void push_up(int u){ if(tr[u].cnt) tr[u].len=tr[u].r-tr[u].l+1; else if(tr[u].l!=tr[u].r) tr[u].len=tr[u<<1].len+tr[u<<1|1].len; else tr[u].len=0; } void build(int u,int l,int r){ tr[u].l=l; tr[u].r=r; if(l==r) return; int mid=(l+r)>>1; build(u<<1,l,mid); build(u<<1|1,mid+1,r); } void modify(int u,int l,int r,int k){ if(tr[u].l>=l && tr[u].r<=r){ tr[u].cnt+=k; push_up(u); return; } int mid=(tr[u].l+tr[u].r)>>1; if(l<=mid) modify(u<<1,l,r,k); if(r>mid) modify(u<<1|1,l,r,k); push_up(u); } int query(int u){ if(tr[u].l==tr[u].r) return tr[u].l; int mid=(tr[u].l+tr[u].r)>>1; int l_len=mid-tr[u].l+1; if(tr[u<<1].len<l_len) return query(u<<1); else return query(u<<1|1); } int main() { scanf("%d %d",&n,&d); for(int i=1;i<=n;++i){ int x1,y1,x2,y2; scanf("%d %d %d %d",&x1,&y1,&x2,&y2); x2--,y2--; if(x2-x1+1>=d) x1=0,x2=d-1; if(y2-y1+1>=d) y1=0,y2=d-1; x1=(x1%d+d)%d,x2=(x2%d+d)%d,y1=(y1%d+d)%d,y2=(y2%d+d)%d; if(x1<=x2){ if(y1<=y2){ add(x1,y1,x2,y2); } else{ add(x1,0,x2,y2); add(x1,y1,x2,d-1); } } else{ if(y1<=y2){ add(0,y1,x2,y2); add(x1,y1,d-1,y2); } else{ add(0,0,x2,y2); add(x1,y1,d-1,d-1); add(0,y1,x2,d-1); add(x1,0,d-1,y2); } } } build(1,0,d-1); for(int i=0;i<d;++i){ for(auto it:seg[i]){ modify(1,it.y1,it.y2,it.k); } if(tr[1].len<d){ puts("YES"); printf("%d %d\n",i,query(1)); return 0; } } puts("NO"); return 0; }