poj 3207(2-SAT+SCC)

传送门:Problem 3207

https://www.cnblogs.com/violet-acmer/p/9769406.html

难点：

　　题意理解。

题意：

　　平面上有一个圆,圆上有n个点(分别编号0-n-1,按顺序在圆上排列),现在要对这n个点连接m条线，这m条线的两个端点已经给出了,这个线可以从圆内连或从圆外连，且任意一个点最多只作为一条线的端点.要求任意两条线不相交,问你是否可能?

　　注意：两点间的连线没说一定是直线。

题解：

　　两直线ab,cd(a < b , c < d)不可以同时在圆内或圆外的条件是 a<c<b<d || c<a<d<b

　　以此构造布尔方程。

AC代码：

 #include<iostream>

 #include<cstdio>

 #include<vector>

 #include<cstring>

 using namespace std;

 #define pb push_back

 #define mem(a,b) (memset(a,b,sizeof a))

 const int maxn=+;

 int n,m;

 int a[maxn],b[maxn];

 int scc[*maxn];

 bool vis[*maxn];

 vector<int >vs;

 vector<int >G[*maxn],rG[*maxn];

 void addEdge(int u,int v)

 {

     G[u].pb(v);

     rG[v].pb(u);

 }

 bool Touch(int a,int b,int c,int d)//判断 ab 是否一定与 cd 相交

 {

     if(a<c && c<b && b<d)

         return true;

     if(c<a && a<d && d<b)

         return true;

     return false;

 }

 void Dfs(int u)

 {

     vis[u]=true;

     for(int i=;i < G[u].size();++i)

     {

         int to=G[u][i];

         if(!vis[to])

             Dfs(to);

     }

     vs.pb(u);

 }

 void rDfs(int u,int k)

 {

     vis[u]=true;

     scc[u]=k;

     for(int i=;i < rG[u].size();++i)

     {

         int to=rG[u][i];

         if(!vis[to])

             rDfs(to,k);

     }

 }

 void SCC()

 {

     mem(vis,false);

     vs.clear();

     for(int i=;i <= *m;++i)

         if(!vis[i])

             Dfs(i);

     mem(vis,false);

     int k=;

     for(int i=vs.size()-;i >= ;--i)

     {

         int to=vs[i];

         if(!vis[to])

             rDfs(to,++k);

     }

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     for(int i=;i <= m;++i)

     {

         scanf("%d%d",a+i,b+i);

         if(a[i] > b[i])

             swap(a[i],b[i]);

         for(int j=;j < i;++j)

         {

             if(Touch(a[i],b[i],a[j],b[j]))

             {

                 addEdge(j+m,i);

                 addEdge(i+m,j);

                 addEdge(j,i+m);

                 addEdge(i,j+m);

             }

         }

     }

     SCC();

     bool flag=false;

     for(int i=;i <= m;++i)

         if(scc[i] == scc[i+m])

             flag=true;

     if(flag)

         printf("the evil panda is lying again\n");

     else

         printf("panda is telling the truth...\n");

 }