2025 United Kingdom and Ireland Programming Contest (UKIEPC 2025) 2025 英国 ICPC——B. Brickwork（判断砖块是否重叠）（扫描线的本质就是遍历一个出一个）（维护一个当前生效的集合）（把二维的问题变为一维的问题来做） · znzryb
## 题目大意
我们试图设计一个墙壁，将其作为2D矩形砖块形状的镶嵌，所有砖块都具有完全的整数坐标和完全的整数大小。
给定这个2D墙壁上砖块的描述，确定墙壁是否确实是一个墙壁——覆盖一个完美的矩形，没有砖块重叠，砖块之间也没有空白空间。这意味着区域内的每个非整数坐标都应该被一个砖块完全覆盖。
分别说明样本1、2和3的砖块图示。
**输入**
- 一行，包含砖块数量 $n$ ($1 \le n \le 1\,000\,000$)。
- $n$ 行，每行描述一个砖块，包括四个整数 $x \ y\ w\ h$ 分别表示 xy 坐标、宽度、高度 ($0 \le x, y \le 10^8$; $1 \le w, h \le 10^8$)。
**说白了就是这个****砖块的位置****，还有****长宽****都告诉你了。呃，但是呢这个砖块的的这个长宽，还有数量比较大。****需要你判断一下这些砖块之间有没有重叠****。**
## 思路讲解
一言以蔽之，我们这道题目所采用的策略就是维护一个在**当前激活的 X 区间上**的**不相交的 Y 区间集合**。也就是说，我们的这个 activates 集合，它里面存储的是 y 区间。然后 activates 的进出是使用的 event 去控制，去顺序遍历 event 以控制 activates 里面的y 区间集合的进出。
其实扫描线思想的精髓呢，其实就是把**二维的问题看成是一维的问题**，通过消除偏序关系，维护激活集合。**维护激活的矩形集合。**等方式。
如果说我们**维护一个集合**，这个集合当中**只有当前还生效的矩形**，我们是不是会轻松很多？
呃，我们先使用event类来模拟这个矩形的进入和删除。
```cpp
struct Event {
ll x,y_st,y_ed,op;
bool operator<(const Event & o) const {
if (x!=o.x) return x<o.x;
return op<o.op;
}
// auto operator<=>(const Event &)const =default;
};
multiset<Event> event_st;
for (int i=0;i<N;++i) {
ll x,y,w,h;
cin>>x>>y>>w>>h;
mnx=min(mnx,x);
mny=min(mny,y);
mxx=max(mxx,x+w);
mxy=max(mxy,y+h);
acc_area+=w*h;
// rect_ls[i]={x,y,w,h};
event_st.insert({x,y,y+h,1});
event_st.insert({x+w,y,y+h,0});
}
```
然后我们去读取 event 类去模拟这个进入和删除的过程，保持 activates 这个Pair set里面只有这个，已经激活的矩形，那么**已经激活的矩形其实就相当于一段线段了（在Y方向上的线段）**。我们使用check函数去检查一下，就是我们插入的这个东西，它会不会呃和activs里面本来就有的这个线段重叠（不过，因为**activates里面的这个所有的线段都是互不重叠的**，所以说判断起来会非常容易，**只需要检查前驱和后继即可**。）。
```cpp
// 如果假设 activates 是这个互不重叠的，那么肯定没问题
set<pair<ll,ll>> activates;
for (auto &event:event_st) {
auto [x,y_st,y_ed,op]=event;
if (op==1) {
if (!check({y_st,y_ed})) {
cout<<"no\n";
return;
}
activates.insert({y_st,y_ed});
}else {
activates.erase({y_st,y_ed});
}
}
cout<<"yes\n";
```
```cpp
auto check=[&](pair<ll,ll> y_pair) -> bool {
if (activates.empty()) {
return true;
}
auto it=activates.upper_bound(y_pair);
if (it!=activates.end()) {
if (y_pair.first>=it->second || y_pair.second<=it->first) {
}else {
return false;
}
}
if (it!=activates.begin()) {
it=prev(it);
if (y_pair.first>=it->second || y_pair.second<=it->first) {
}else {
return false;
}
}
return true;
};
```
## AC代码
AC
[https://qoj.ac/submission/2011619](https://qoj.ac/submission/2011619)
::: 只能够通过 qoj 数据的错解
```cpp
/**
* Problem: B. Brickwork
* Contest: 2025 United Kingdom and Ireland Programming Contest (UKIEPC 2025)
* Judge: Codeforces
* URL: https://codeforces.com/gym/106157/problem/B
* Created: 2026-02-07 00:00:00
* Author: Gospel_rock
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT,testcase;
/*
*
*/
struct Rectangle {
ll x,y,w,h;
bool operator<(const Rectangle &o) const {
if (x+w!=o.x+o.w) {
return x+w<o.x+o.w;
}
return h+y<o.h+o.y;
}
};
void Solve() {
ll N;
cin >> N;
ll mnx=INF,mny=INF,mxx=0,mxy=0;
ll acc_area=0;
vector<Rectangle> rect_ls(N);
for (int i=0;i<N;++i) {
ll x,y,w,h;
cin>>x>>y>>w>>h;
mnx=min(mnx,x);
mny=min(mny,y);
mxx=max(mxx,x+w);
mxy=max(mxy,y+h);
acc_area+=w*h;
rect_ls[i]={x,y,w,h};
}
// 用总面积和这个覆盖面积比，如果不相等，说明一定发生了空缺或者重叠
if ((mxx-mnx)*(mxy-mny)!=acc_area) {
cout<<"no\n";
return;
}
// 需要判断各个矩形之间是否有重叠，有重叠输出 no
// 我们的想法就是先根据 x,y 排序
// 我们最好使用这个结束位置排序
sort(all(rect_ls));
for (int i=1;i<N;++i) {
auto [x1,y1,w1,h1]=rect_ls[i-1];
auto [x2,y2,w2,h2]=rect_ls[i];
if (x2>=x1+w1) {
continue;
}
if (y2>=y1+h1 || y2+h2<=y1) {
continue;
}
cout<<"no\n";
return;
}
cout<<"yes\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
// cin >> lT;
// for (testcase=1;testcase<=lT;++testcase)
Solve();
return 0;
}
/*
AC
https://qoj.ac/submission/2011619
*/
```
:::
AC
[https://codeforces.com/gym/106157/submission/361754040](https://codeforces.com/gym/106157/submission/361754040)
[https://qoj.ac/submission/2011657](https://qoj.ac/submission/2011657)
::: 正解
```cpp
/**
* Problem: B. Brickwork
* Contest: 2025 United Kingdom and Ireland Programming Contest (UKIEPC 2025)
* Judge: Codeforces
* URL: https://codeforces.com/gym/106157/problem/B
* Created: 2026-02-07 02:16:01
* Author: Gospel_rock
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT,testcase;
/*
*
*/
struct Rectangle {
ll x,y,w,h;
bool operator<(const Rectangle &o) const {
if (x+w!=o.x+o.w) {
return x+w<o.x+o.w;
}
return h+y<o.h+o.y;
}
};
struct Event {
ll x,y_st,y_ed,op;
bool operator<(const Event & o) const {
if (x!=o.x) return x<o.x;
return op<o.op;
}
// auto operator<=>(const Event &)const =default;
};
void Solve() {
ll N;
cin >> N;
ll mnx=INF,mny=INF,mxx=0,mxy=0;
ll acc_area=0;
// vector<Rectangle> rect_ls(N);
multiset<Event> event_st;
for (int i=0;i<N;++i) {
ll x,y,w,h;
cin>>x>>y>>w>>h;
mnx=min(mnx,x);
mny=min(mny,y);
mxx=max(mxx,x+w);
mxy=max(mxy,y+h);
acc_area+=w*h;
// rect_ls[i]={x,y,w,h};
event_st.insert({x,y,y+h,1});
event_st.insert({x+w,y,y+h,0});
}
// 如果假设 activates 是这个互补重叠的，那么肯定没问题
set<pair<ll,ll>> activates;
auto check=[&](pair<ll,ll> y_pair) -> bool {
if (activates.empty()) {
return true;
}
auto it=activates.upper_bound(y_pair);
if (it!=activates.end()) {
if (y_pair.first>=it->second || y_pair.second<=it->first) {
}else {
return false;
}
}
if (it!=activates.begin()) {
it=prev(it);
if (y_pair.first>=it->second || y_pair.second<=it->first) {
}else {
return false;
}
}
return true;
};
for (auto &event:event_st) {
auto [x,y_st,y_ed,op]=event;
if (op==1) {
if (!check({y_st,y_ed})) {
cout<<"no\n";
return;
}
activates.insert({y_st,y_ed});
}else {
activates.erase({y_st,y_ed});
}
}
cout<<"yes\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
// cin >> lT;
// for (testcase=1;testcase<=lT;++testcase)
Solve();
return 0;
}
/*
AC
https://codeforces.com/gym/106157/submission/361754040
*/
```
:::
## 心路历程（WA，TLE，MLE……）