CF1503F Balance the Cards【构造+平面几何】

CF1503F Balance the Cards

题面

给定 $2n$ ($1\le n\le 2?10^5$) 对数 $a_i$, $b_i$，其中 $a_i$ 和 $b_i$ 分别是 $1,?1,2,?2,\dots ,n,?n$ 的排列。$x>0$ 表示第 $x$ 种左括号，$x<0$ 表示第 $?x$ 种右括号。你需要将这 $2n$ 对数重新排列，使得 $a_i$ 和 $b_i$ 分别是合法括号序列。

简要题解

把每一张牌看成一个点，从 $x$ 向 $?x$ 连边（存在 $a,b$ 两类边），每个点的度数都是 $2$ ，所以得到的图会是若干个环组成，而且 $a$ 和 $b$ 的边交替出现。

考虑构造，如果存在 $u\to v\to w$ 则可以将这三个点合并成一个点 ，例如 $(a,b)\to (c,?b)\to (?c,d)$可以合并成 $(a,d)$ 。重复这个操作，如果最后能缩成只剩两个点 $(a,b),(?a,?b)$ 则构造出一组解。

证明这样构造是充要的：
这样构造能求出解的条件是，给一个环任意指定一个正方向为顺时针，顺时针方向的 $a$ 类边和 $b$ 类边的边数相差为 $1$ （因为每次合并三个点就是删掉了某个方向上的一条 $a$ 边一条 $b$ 边）。首先这是充分的，接下来证明必要性。
考虑一个合法的序列，在 $x$ 和 $?x$ 之间画一个半圆，$a$ 在下面，$b$ 在上面。因为是合法括号序列，每个连通块都是简单回路。考虑一个点沿着回路走一圈面对的方向越过 $x$ 轴正方向的次数就可以知道上文所说的条件是必要的。

#include <bits/stdc++.h>
#define N 800015
using namespace std;
const int o=200005;
int n,pos_a[N],pos_b[N],cnt;
struct node{
    int a,b,u,v,w,id;node(int A,int B,int U=0,int V=0,int W=0){
     a=A,b=B,u=U,v=V,w=W; }
};
queue<int> q;
vector<node> ans,cc;
bool tag[N];
int to(int x){
     return o+o-x; }
bool cmp(node x,node y){
     return abs(x.a-o)==abs(y.a-o)?abs(x.b-o)<abs(y.b-o):abs(x.a-o)<abs(y.a-o);
}
void print(int x){
    if(cc[x].u==0) cout<<cc[x].a-o<<' '<<cc[x].b-o<<'\n';else print(cc[x].u),print(cc[x].v),print(cc[x].w);
}
int main(){
    cin>>n;int x,y; cc.push_back(node(0,0));for(int i=1;i<=n+n;i++){
    cin>>x>>y; x+=o,y+=o;++cnt,cc.push_back(node(x,y)); pos_a[x]=i,pos_b[y]=i;cc[i].id=i;if((x<o&&o<y)||(y<o&&o<x)) q.push(i);}while(!q.empty()){
    x=q.front(); q.pop();if(tag[x]) continue;int u=pos_a[to(cc[x].a)],v=pos_b[to(cc[x].b)];if(u==v){
     cout<<"NO"; return 0; }if(cc[x].a>o) ++cnt,cc.push_back(node(cc[v].a,cc[u].b,v,x,u));else ++cnt,cc.push_back(node(cc[v].a,cc[u].b,u,x,v));tag[v]=tag[u]=tag[x]=1; pos_a[cc[cnt].a]=cnt,pos_b[cc[cnt].b]=cnt;cc[cnt].id=cnt;if((cc[cnt].a<o&&o<cc[cnt].b)||(cc[cnt].b<o&&o<cc[cnt].a)) q.push(cnt);}for(int i=1;i<=cnt;i++) if(!tag[i]) ans.push_back(cc[i]);sort(&ans[0],&ans[ans.size()],cmp);for(int i=0;i<ans.size();i+=2){
    if(ans[i].a!=to(ans[i+1].a)||ans[i].b!=to(ans[i+1].b)){
     cout<<"NO"; return 0; }if(ans[i].a<o&&ans[i].b>o){
     cout<<"NO"; return 0; }if(ans[i].a>o&&ans[i].b<o){
     cout<<"NO"; return 0; }if(ans[i].a<o) swap(ans[i],ans[i+1]);}cout<<"YES\n";for(int i=0;i<ans.size();i++) print(ans[i].id);
}