【AtCoder Regular Contest 076 E】Connected? | Mrsrz's blog

括号匹配。

题目大意：

给定一个矩形区域上的若干对点，要求用曲线连接每一对点，并满足：

• 曲线不相交。
• 曲线不超出矩形的边界。

问是否存在合法方案。

题解：

发现只有两个端点都在边界上的点对才会对答案产生影响，而一个端点在中间的情况，必定可以通过曲折来满足条件。

我们将边界看成一个环，那么一个点对会将一段区间分成两个部分。如果一个点对的两个端点已经在不同部分了，那么就没有合法方案了。

我们可以使用括号匹配来完成。将第一个端点看成左括号，第二个端点看成右括号，则这对括号将一个段分成括号内和括号外两部分。

如果最后括号匹配合法，则有方案，否则无方案。

Code：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N=1e5+6;
int n,sta[N],top,R,C;
bool vis[N];
vector<pair<int,int> >v[4];
inline bool chk(int x,int y){return x==0||x==R||y==0||y==C;}
void push(int r,int c,int id){
    if(!r)v[0].emplace_back(c,id);else if(c==C)v[1].emplace_back(r,id);else
    if(r==R)v[2].emplace_back(C-c,id);else v[3].emplace_back(R-r,id);
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>R>>C>>n;
    for(int i=1;i<=n;++i){
        int r1,c1,r2,c2;
        cin>>r1>>c1>>r2>>c2;
        if(chk(r1,c1)&&chk(r2,c2))push(r1,c1,i),push(r2,c2,i);
    }
    for(int i=0;i<4;++i){
        sort(v[i].begin(),v[i].end());
        for(auto x:v[i]){
            int id=x.second;
            if(!vis[id])sta[++top]=id,vis[id]=1;else if(!top||sta[top]!=id){cout<<"NO\n";return 0;}else --top;
        }
    }
    cout<<"YES\n";
    return 0;
}