2021牛客暑期多校训练营6 - H - Hopping Rabbit（扫描线）

72 阅读 0 评论 48 点赞

我是靠谱客的博主平淡大雁，最近开发中收集的这篇文章主要介绍2021牛客暑期多校训练营6 - H - Hopping Rabbit（扫描线），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接：点击进入

题目

在这里插入图片描述

题意

n 个矩形，给定 d ，找一个位置 ( x , y ) ( x = $x_0$ + 0.5 , y = $y_0$ + 0.5 ) ，使所有点（ x + k * d , y + k * d ）( k 任意整数 ) 均不落在矩形内，若存在输出 “ YES ” 以及 $x_0$ , $y_0$ ；否则输出 " NO " 。

思路

我们可以将所有的矩形移动到 ( 0 , 0 ) 到 ( d , d ) 范围内，然后看所有矩形的并有没有将 ( 0 , 0 ) 到 ( d , d ) 这个范围完全覆盖，如果完全被覆盖，那说明没有可以出发的点，否则就存在可以出发的点。
那么问题就转换成了将 n 个矩形移动到 ( 0 , 0 ) 到 ( d , d ) 范围内求并，这不就是扫描线。移动的话，我们对矩形的坐标用 d 取模即可 ( 注：取模后可能会形成 1 个或 2 个或 4 个矩形，分类讨论一下即可 )。
然后剩下的就是扫描线维护了。因为这个题要输出这个点，所以我们用线段树维护区间覆盖次数的最小值，当扫描到某一行发现存在最小值为 0 的情况，说明至少有一个点是没有被覆盖的，那么直接再在树上遍历找这个点即可。
( 由于要找的点实际上是 ( x + 0.5 , y + 0.5 ) ，因此即使 ( x , y ) 在上边界或者右边界上也是可以的 ( 正常平面直角坐标系中 )，但是我们要是覆盖查找的话，上、右边界的点会被覆盖排除掉，因此我们要对 x2-- , y2-- ）

代码

//#pragma GCC optimize(3)//O3
//#pragma GCC optimize(2)//O2
#include<iostream>
#include<string>
#include<map>
#include<set>
//#include<unordered_map>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<stack>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<fstream>
#define X first
#define Y second
#define best 131 
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int,int>
#define lowbit(x) x & -x
#define inf 0x3f3f3f3f
// #define int long long
//#define double long double
//#define rep(i,x,y) for(register int i = x; i <= y;++i)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double pai=acos(-1.0);
const int maxn=1e5+10;
const int N=5e3+10;
const int mod=998244353;
const double eps=1e-9;
/*--------------------------------------------*/
inline int read()
{
    int k = 0, f = 1 ;
    char c = getchar() ;
    while(!isdigit(c)){if(c == '-') f = -1 ;c = getchar() ;}
    while(isdigit(c)) k = (k << 1) + (k << 3) + c - 48 ,c = getchar() ;
    return k * f ;
}
/*--------------------------------------------*/

int n,x[maxn],d,flag,ans1;
struct node
{
	int l;
	int r;
	int x;
};
vector<node>v[maxn];
struct Node  
{
	int l;
	int r;
	int lazy;
	int minn;
}t[maxn<<2];
void pushup(int p)
{
	t[p].minn=min(t[p<<1].minn,t[p<<1|1].minn);
}
void pushdown(int p)
{
	if(t[p].lazy)
	{
		t[p<<1].minn+=t[p].lazy;
		t[p<<1|1].minn+=t[p].lazy;
		t[p<<1].lazy+=t[p].lazy;
		t[p<<1|1].lazy+=t[p].lazy;
		t[p].lazy=0;
	}
}
void build(int p,int l,int r) 
{
	t[p].l=l,t[p].r=r,t[p].lazy=0;
	if(l==r) 
	{
		t[p].minn=0;
		return;
	}
	int mid=l+r>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	pushup(p);
}
void change(int p,int l,int r,int x) 
{
	if(l<=t[p].l&&t[p].r<=r) 
	{
		t[p].minn+=x;
		t[p].lazy+=x;
		return ;
	}
	pushdown(p);
	int mid=t[p].l+t[p].r>>1;
	if(l<=mid) change(p<<1,l,r,x);
	if(r>mid) change(p<<1|1,l,r,x);
	pushup(p);
}
void print(int p,int l,int r) 
{
	if(l==r) 
	{
		if(t[p].minn==0) 
		{
			flag=1;
			ans1=l;
		}
		return ;
	}
	pushdown(p);
	int mid=l+r>>1;
	print(p<<1,l,mid);
	if(flag) return ;
	print(p<<1|1,mid+1,r);
}
void add(int x1,int x2,int y1,int y2)
{
	v[y1].push_back({x1,x2,1});
	v[y2+1].push_back({x1,x2,-1});
}
int main()
{
//	ios::sync_with_stdio(false);
//	cin.tie(0);cout.tie(0);
	cin>>n>>d;
	for(int i=1;i<=n;i++)
	{
		int x1,x2,y1,y2;
		cin>>x1>>y1>>x2>>y2;
		x2--,y2--;
		if(x1-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,x2,y1,y2);
			else
				add(x1,x2,y1,d-1),add(x1,x2,0,y2);
		}
		else
		{
			if(y1<=y2)
				add(0,x2,y1,y2),add(x1,d-1,y1,y2);
			else
				add(0,x2,y1,d-1),add(0,x2,0,y2),add(x1,d-1,y1,d-1),add(x1,d-1,0,y2);
		}
	}
	build(1,0,d-1);
	for(int i=0;i<d;i++)
	{
		for(auto t:v[i])
			change(1,t.l,t.r,t.x);
		if(t[1].minn==0)
		{
			print(1,0,d-1);
			cout<<"YES"<<endl;
			cout<<ans1<<" "<<i<<endl;
			return 0;
		}
	}
	cout<<"NO"<<endl;
	return 0; 
}