题目大意：
在圆上顺时针n个点，给定m个连接，可以通过圆内或者圆外相交，问能不能找到一种方式，使这些连接的边都不相交
这里很容易看出的是，这些边只有在圆外或者圆内两种连接方式，而且必须选择其中一种
所以2-sat以这些边作为连接点，向内连接为2*i，圆外连接为2*i+1
自己画画图可以找到规律
if(b[i]<a[j] || b[j]<a[i] || (a[i]<a[j]&&b[i]>b[j]) || (a[j]<a[i]&&b[j]>b[i])) ;这个时候，两条边不管在什么地方都不会影响的
其他的情况就必须保证一条在圆内一条在圆外
1 #include <cstdio> 2 #include <vector> 3 #include <iostream> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7 #define N 2010 8 int S[N] , n , m , c; 9 bool mark[N]; 10 vector<int> G[N]; 11 12 void init() 13 { 14 memset(mark , 0 , sizeof(mark)); 15 for(int i=0 ; i<2*m ; i++) G[i].clear(); 16 } 17 18 void add_clause(int i , int p , int j , int q) 19 { 20 int m=2*i+p , n=2*j+q; 21 G[m^1].push_back(n); 22 G[n^1].push_back(m); 23 } 24 25 bool dfs(int u) 26 { 27 if(mark[u]) return true; 28 if(mark[u^1]) return false; 29 mark[u] = true; 30 S[c++] = u; 31 for(int i=0 ; i<(int)G[u].size() ; i++) 32 if(!dfs(G[u][i])) return false; 33 return true; 34 } 35 36 bool solve() 37 { 38 for(int i=0 ; i<2*m ; i+=2){ 39 if(!mark[i] && !mark[i^1]){ 40 c = 0; 41 if(!dfs(i^1)){ 42 while(c) mark[S[--c]] = false; 43 if(!dfs(i)) return false; 44 } 45 } 46 } 47 return true; 48 } 49 50 int main() 51 { 52 //freopen("in.txt" , "r" , stdin); 53 while(~scanf("%d%d" , &n , &m)) 54 { 55 init(); 56 int a[N] , b[N]; 57 for(int i=0 ; i<m ; i++){ 58 scanf("%d%d" , &a[i] , &b[i]); 59 if(a[i]>b[i]) swap(a[i] , b[i]); 60 for(int j=0 ; j<i ; j++){ 61 if(b[i]<a[j] || b[j]<a[i] || (a[i]<a[j]&&b[i]>b[j]) || (a[j]<a[i]&&b[j]>b[i])) ; 62 else { 63 // cout<<i<<" "<<j<<endl; 64 add_clause(i , 0 , j , 0); 65 add_clause(i , 1 , j , 1); 66 } 67 } 68 } 69 printf("%s " , solve()?"panda is telling the truth...":"the evil panda is lying again"); 70 } 71 }