Niuke 2021 summer training 6-h-hopping rabbit

Cattle guest 2021 Summer training 6-H-Hopping Rabbit

Topic link

The question

There is... On the plane $n$ A rectangle , Given $d$, Need to find a place $(x,y)$, Make all $(x+kd,y+kd)$ Do not fall in the rectangle

Answer key

Pre knowledge ： Scan line
Because the positions that can be reached are repeated , We move all rectangles to $(0,0)$ To $(d,d)$ Join in range , If there are uncovered points in the final range , Then this point can be used as the answer . Rectangle Union , Use scanning line .
Move to $(d,d)$ It may be disassembled into $1,2,4$ A rectangle

At the same time, because the title gives a rectangle , And the little rabbit is at the midpoint of the rectangle , So rectangular $x_2$ It can be stepped on , Let's move the edge to the midpoint ,$x_1,x_2$ It becomes $x_1,x_2-1$,$y$ Empathy .
Other things are explained in the code

Code

#include<bits/stdc++.h>
#define PR pair<int,int>
#define Fi first
#define Se second
#define Mp make_pair
#define Pb push_back
using namespace std;
const int N=1e5+9;
int n,d;
int t[N*4],vis[N*4];
vector<PR>e1,e2,s1[N],s2[N];
void Change(int u,int l,int r,int y1,int y2,int flag)
{
    
	if(y1<=l&&r<=y2)
	{
    
		t[u]+=flag;
		vis[u]+=flag; //vis Indicates the interval l~r Number of matrices  
		return;
	}
	int mid=(l+r)/2;
	if(y1<=mid) Change(u*2,l,mid,y1,y2,flag);
	if(y2>mid) Change(u*2+1,mid+1,r,y1,y2,flag);
	t[u]=min(t[u*2],t[u*2+1])+vis[u];
}
int Ask(int u,int l,int r)
{
    
	if(l==r) return l;
	int mid=(l+r)/2;
	if(t[u]==t[u*2]+vis[u]) return Ask(u*2,l,mid); //23 Line code  
	else return Ask(u*2+1,mid+1,r);
}
int main()
{
    
	cin>>n>>d;
	int P=(1<<30)/d*d; // Less than or equal to  1<<30  Maximum d Multiple  
	for(int i=1;i<=n;i++)
	{
    
		int x1,x2,y1,y2;
		cin>>x1>>y1>>x2>>y2;
		x1+=P; y1+=P; x2+=P; y2+=P; // add d The multiple of is guaranteed to be positive  
		e1.clear(); e2.clear();
		if(x2-x1>=d) e1.Pb(Mp(0,d-1)); // Fill up d 
		else if(x1%d<=(x2-1)%d) e1.Pb(Mp(x1%d,(x2-1)%d)); //x Not more than d 
		else // More than d, Divided into two groups. x 
		{
    
			e1.Pb(Mp(x1%d,d-1));
			e1.Pb(Mp(0,(x2-1)%d));
		}
		if(y2-y1>=d) e2.Pb(Mp(0,d-1));
		else if(y1%d<=(y2-1)%d) e2.Pb(Mp(y1%d,(y2-1)%d));
		else
		{
    
			e2.Pb(Mp(y1%d,d-1));
			e2.Pb(Mp(0,(y2-1)%d));
		}
		// Only split into a rectangle ： One x, One y
		// Split it into two ： One x Two y, Or two x One 
		// Split into four ： Two x, Two y
		for(auto j:e1) // parallel y The scanning line of the camera  
		{
    
			for(auto k:e2)
			{
    
				s1[j.Fi].Pb(k); // The previous one y by +1 
				s2[j.Se+1].Pb(k); //j.Fi~j.Se by +1,x=j.Se+1 Subtract  
			}
		}
	}
	for(int i=0;i<d;i++) // Scan line  
	{
    
		for(auto j:s1[i])
			Change(1,0,d-1,j.Fi,j.Se,1);
		for(auto j:s2[i])
			Change(1,0,d-1,j.Fi,j.Se,-1);
		if(!t[1]) // if t1==0, It means that there is no line covering 0~d-1 And one thing is 0 
		{
    
			printf("YES\n%d %d\n",i,Ask(1,0,d-1));
			return 0;
		}
	}
	printf("NO\n");
	return 0;
}