题意：在一个圆上顺时针安放着n个点，给出m条线段连接端点，要求线段不相交，线段可以在圆内也可以在圆外，问是否可以。
思路：假设一条线段，放在圆外是A,放在园内是A'，那么两条线段如果必须一个放圆内一个放圆外的条件就是 端点区间相交（严格相交），所以就建立了2-SAT模型，然后跑2-SAT的模板就可以了。
//#include<bits/stdc++.h> #include<stdio.h> #include<iostream> #include<stdlib.h> #include<string.h> #define clr(a,b) memset(a,b,sizeof(a)) typedef long long ll; using namespace std; const int maxn=250010; bool vis[maxn<<1]; int n,m; int head[maxn<<1],tot; struct edge{ int to,Next; }a[maxn<<1]; struct node{ int x,y; }b[maxn]; void addv(int u,int v){ a[++tot].to=v; a[tot].Next=head[u]; head[u]=tot; } int top,sta[maxn<<1]; bool dfs(int u){ if(vis[u^1])return false; if(vis[u])return true; vis[sta[++top]=u]=1; for(int i=head[u];i!=-1;i=a[i].Next) { int v=a[i].to; if(!dfs(v))return false; } return true; } bool Two_sat(){ for(int i=0;i<(n<<1);i+=2) { if(vis[i]||vis[i^1])continue; top=0; if(!dfs(i)){ while(top)vis[sta[top--]]=0; if(!dfs(i^1))return false; } } return true; } bool cal(int i,int j){ if(b[i].x<b[j].x&&b[j].x<b[i].y&&b[i].y<b[j].y)return true; swap(i,j); if(b[i].x<b[j].x&&b[j].x<b[i].y&&b[i].y<b[j].y)return true; return false; } int main(){ clr(head,-1); cin>>n>>m; int u,v; for(int i=1;i<=m;i++) { scanf("%d%d",&b[i].x,&b[i].y); } for(int i=1;i<=m;i++) { for(int j=i+1;j<=m;j++) { if(cal(i,j)){ addv(i<<1,j<<1|1); addv(i<<1|1,j<<1); } } } if(Two_sat()){ printf("panda is telling the truth... "); }else{ puts("the evil panda is lying again"); } }