[ABC338E] Chords

CJ_Fu · 2024-01-30 08:44:42 · 题解

E - Chords

翻译

在一个圆上有 2N 个点，N 条弦，弦的端点为 (A_i,B_i)，问是否有弦相交。

题解

将圆展开，弦的端点即对应区间 [A_i,B_i]，然后看是否有相交（不包括内含）的区间即可。
时间复杂度 O(N)。
借用官方题解的图：

#include<bits/stdc++.h>
using namespace std;
int n,a[200003],b[200003],p[400003];
int stk[400003],top;
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i]>>b[i],p[a[i]]=p[b[i]]=i;
    // p 数组打标记，记录每条弦的两个端点位置
    for(int i=1;i<=2*n;i++){
        stk[++top]=p[i];
        while(top>=2&&stk[top]==stk[top-1]) top-=2;
        // 类似括号序列
    }
    // 若栈不空则说明有相交
    if(top) cout<<"Yes";
    else cout<<"No";
    return 0;
}

挺短的，而且感觉 E<D。