一个圆上顺时针排放n给点，给出m条线段，要么在圆内，要么在圆外，问是否可以使这m条线段不相交
如果两条线段i和j相交，那么i->~j, j->~i, ~i->j, ~j->i，不能同时在圆内或圆外
很巧妙的将边看成顶点，利用2-SAT解决
代码：
#include<iostream> #include<stack> using namespace std; const int MAX=1005; struct node { int v,next; }g[MAX*MAX]; int adj[MAX],dfn[MAX],low[MAX],inStack[MAX],bel[MAX],x[MAX],y[MAX]; int n,m,e,index,cnt; stack<int>s; void add(int u,int v) { g[e].v=v; g[e].next=adj[u]; adj[u]=e++; } void tarjan(int u) { dfn[u]=low[u]=++index; s.push(u); inStack[u]=1; int i,v; for(i=adj[u];i!=-1;i=g[i].next) { v=g[i].v; if(!dfn[v]) { tarjan(v); low[u]=min(low[u],low[v]); } else if(inStack[v]) low[u]=min(low[u],dfn[v]); } if(dfn[u]==low[u]) { cnt++; do { v=s.top(); s.pop(); inStack[v]=0; bel[v]=cnt; }while(u!=v); } } int main() { int i,j; scanf("%d%d",&n,&m); e=index=cnt=0; memset(dfn,0,sizeof(dfn)); memset(adj,-1,sizeof(adj)); for(i=1;i<=m;i++) { scanf("%d%d",&x[i],&y[i]); } for(i=1;i<=m;i++) { for(j=1;j<=m;j++) { if((x[i]<x[j]&&y[i]<y[j]&&y[i]>x[j]))//第i条线段和第j条线段相交 { add(2*i+1,2*j); add(2*j+1,2*i); add(2*i,2*j+1); add(2*j,2*i+1); } } } for(i=1;i<=2*m;i++) { if(!dfn[i]) tarjan(i); } int flag=1; for(i=1;i<=m;i++) { if(bel[2*i]==bel[2*i+1]) { flag=0; break; } } if(flag) puts("panda is telling the truth..."); else puts("the evil panda is lying again"); return 0; }
