链接:https://ac.nowcoder.com/acm/contest/11257/H
来源:牛客网
题目描述
Little Rabbit loves hopping. He always hops around on the grassland. But dangers are lurking there --- the hunters have set nn traps. Once Little Rabbit falls into a trap, his life will be threatened. Therefore, Little Rabbit has to keep away from those traps.
Let's use two-dimensional Cartesian coordinate system to describe the grassland. We can regard Little Rabbit as a point, and regard traps as rectangles on the plane. The sides of the rectangles are parallel to the coordinate axes. We use two points to describe a rectangle --- the lower left point (x1,y1)(x1,y1) and the upper right point (x2,y2)(x2,y2) (x1<x2x1<x2, y1<y2y1<y2, x1,y1,x2,y2x1,y1,x2,y2 are all integers).
Little Rabbit can hop in the direction of xx-axis or yy-axis. The length of each hop is dd. Formally, if Little Rabbit locates at (x,y)(x,y), he can then hop to (x−d,y)(x−d,y), (x+d,y)(x+d,y), (x,y−d)(x,y−d) or (x,y+d)(x,y+d).
Little Rabbit wants to find an initial position (x0+0.5,y0+0.5)(x0+0.5,y0+0.5) (x0x0 and y0y0 are integers) so that when he starts to hop from this point, no matter how he hops, he will never fall into a trap. Please help Little Rabbit to find such a point.
Please note that during a hop, Little Rabbit is in the air and won't fall into a trap. Little Rabbit will fall into a trap only if his landing point is in a trap.
输入描述:
The first line contains two integers nn and dd (1≤n,d≤1051≤n,d≤105) --- the number of traps and the length of each hop.
Then in the next nn lines, each line contains four integers x1,y1,x2,y2x1,y1,x2,y2 (−109≤x1,y1,x2,y2≤109−109≤x1,y1,x2,y2≤109, x1<x2x1<x2, y1<y2y1<y2) --- the lower left point and the upper right point of the rectangle.
It's possible that the rectangles will intersect with each other.
输出描述:
If there exist valid answers, output YES in the first line. Then output two integers x0,y0x0,y0 (−109≤x0,y0≤109−109≤x0,y0≤109) separated by a space in the second line, indicating a valid initial position (x0+0.5,y0+0.5)(x0+0.5,y0+0.5). If there are multiple answers, output any.
If there are no valid answers, output NO in a single line.
示例1
输入
复制
2 2
1 1 2 2
2 2 3 3
输出
复制
YES
3 2
示例2
输入
复制
1 1
1 1 2 2
输出
复制
NO
因为从横坐标x, x + d, x + 2d....以及从坐标y, y + d, y + 2d...这些位置跳的结果都是相同的(即题解说的“能到的位置是周期重复的”),因此可以看做把整个平面用间隔为d的横纵网格线隔开,为方便起见设x轴和y轴也是网格线。那么整个平面就被分为若干个小正方形。把这些正方形摞在一起,如果还有空白区域的话说明是有解的。这就是经典的矩形求并的扫描线算法。由于这个题给的矩形坐标都是整数,因此需要“化点为块”,考虑边界问题。设矩形的真实坐标为(x1, y1)(x2, y2),那么转化为扫描线算法的线段就是(x1, y1, y2 - 1, 1)(左边界)以及(x2, y1, y2 - 1, -1)(右端点),这里的四元组定义参考蓝书线段树一节。因为d的范围不大,考虑用桶存x轴每个位置对应的四元组。依次遍历0到d - 1,对于每个位置先取出其所有四元组进行change操作,然后查询目前是否有位置没有被覆盖,如果有的话则遍历这一列,枚举每个位置找到没有被覆盖的那一个作为答案即可。这样就需要我们的线段树支持区间修改以及区间查询最小值。那么就剩下最后一个问题:如何把整个矩形分割?注意到,不论矩形有多大是什么形状,最终起作用的至多不超过四块。举个例子,设d = 2, 矩形为(1, 1)(5, 3),此时矩形被网格线分成了六块,但实际起作用的只有中间的两块(剩下的分别被这两块覆盖了),因此分类讨论一下即可。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;
ll d;
struct line {//表示为线的矩形的左右边界
ll x, y1, y2;
ll add;
};
bool cmp(line a, line b) {
return a.x < b.x;
}
struct SegmentTree {
ll p, l, r, val, mn, add;//mn是子区间覆盖次数最小值,add是延迟标记
} t[200005 * 4];
void build(ll p, ll l, ll r) {
t[p].l = l, t[p].r = r;
t[p].mn = 0;
if(l == r) {
return;
}
ll mid = (l + r) >> 1;
build(2 * p, l, mid);
build(2 * p + 1, mid + 1, r);
return;
}
void spread(ll p) {
if(t[p].add != 0) {
t[2 * p].mn +=t[p].add;
t[2 * p + 1].mn +=t[p].add;
t[2 * p].add += t[p].add;//!!!!!!
t[2 * p + 1].add += t[p].add;
t[p].add = 0;
}
}
void change(ll p, ll L, ll R, ll v) {
if(t[p].l >= L && t[p].r <= R) {
t[p].mn += v;//整个已经覆盖了
t[p].add += v;
return;
}
spread(p);
ll mid = (t[p].l + t[p].r) >> 1;
if(L <= mid) change(2 * p, L, R, v);
if(R > mid) change(2 * p + 1, L, R, v);
t[p].mn = min(t[2 * p].mn, t[2 * p + 1].mn);
}
ll ask(ll p, ll L, ll R) {
if(t[p].l >= L && t[p].r <= R) {
return t[p].mn;
}
spread(p);
int mid = (t[p].l + t[p].r) >> 1;
ll ret = 0x3f3f3f3f;
if(L <= mid) ret = min(ret, ask(2 * p, L, R));
if(R > mid) ret = min(ret, ask(2 * p + 1, L, R));
return ret;
}
vector<line> Line[100005];//如果写成vector<vector<line> > Line(d + 5)会报非常奇怪的错
void add(ll x1, ll y1, ll x2, ll y2) {////注意这里(0, 0)(0, 0)实际上代表(0, 0)(1, 1)这个矩形
Line[x1].push_back({x1, y1, y2, 1});
Line[x2 + 1].push_back({x2 + 1, y1, y2, -1});//注意这里是x2 + 1 类似差分的思想
}
int main() {
cin >> n >> d;
for(int i = 1; i <= n; i++) {
ll x1, y1, x2, y2;
cin >> 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(x2 >= x1) {//不要忘记取等号 //把一个矩形分为1、2或4个矩形
if(y2 >= y1) {
add(x1, y1, x2, y2);
} else {
add(x1, y1, x2 ,d - 1);
add(x1, 0, x2 ,y2);
}
} else {
if(y2 >= y1) {
add(x1, y1, d - 1, y2);
add(0, y1, x2, y2);
} else {
add(x1, y1, d - 1, d - 1);
add(0, y1, x2, d - 1);
add(x1, 0, d - 1, y2);
add(0, 0, x2, y2);
}
}
}
build(1, 0, d - 1);
ll ansx = -1, ansy = -1;
for(ll i = 0; i < d; i++) {
if(ansx != -1) break;
for(auto l : Line[i]) {
change(1, l.y1, l.y2, l.add);//必须先修改再查询
}
if(ask(1, 0, d - 1) == 0) {//如果有没有被覆盖的位置
for(ll j = 0; j <= d - 1; j++) {
if(ask(1, j, j) == 0) {
ansx = i, ansy = j;
break;
}
}
}
}
if(ansx != -1) {
puts("YES");
cout << ansx << " " << ansy << endl;
} else {
puts("NO");
}
return 0;
}
// 3 4
// 0 0 2 2
// 1 0 3 4
// 0 2 4 4