题目来源：
http://poj.org/problem?id=3207
题意：
平面上有一个圆,圆上有n个点(分别编号0-n-1,按顺序在圆上排列),现在要对着n个点连接m条线，这m条线的两个端点已经给出了(但是没说这些先是连内圈还是连外圈),这个线可以从圆内连或从圆外连.且任意一个点最多只作为一条线的端点.要求任意两条线不相交,问你是否可能?
分析：
由于题目中需要连接的边都确定给出了，我们可以根据任意两线i与j的端点推断出当i与j同时在圆内或圆外是否一定会相交。
如果边i与j同在圆的一侧必定相交，那么边i与边j必然一个在圆内，一个在圆外，所以有如下结论：
i在圆内或j在圆内 且 i在圆外或j在圆外 (想想为什么)
那么如何判断边i(ui,vi) 与 j(uj,vj) 在圆同一侧时一定会相交呢？
由于这里端点是在圆上的，所以如果j边的两点中，一点处于i边两端点的ui顺时针走向vi的圆弧内，一点处于i边两端点的vi顺时针走向ui的圆弧内，那么i与j在圆同一侧时一定相交。否则一定不想交。
代码：
#include<iostream>
#include<cstring>
#include<stack>
#include<iomanip>
#include<cmath>
#include<queue>
#include<algorithm>
#include<stdio.h>
using namespace std;
# define ll long long
const int maxn=1010;
const int maxm=410000;
int op[maxn],vis[maxn],low[maxn],dfn[maxn];
int pt[maxn],stk[maxn],color[maxn],pos[maxn],deg[maxn];
vector<int>vc[maxm],vc2[maxm];struct node
{int x;int y;
}p[maxn],hate[maxn],like[maxn],s1,s2,tmp;
int a,b,dis[maxn],slen;
int x[maxn],y[maxn];
int dist(node aa,node bb)
{return abs(aa.x-bb.x)+abs(aa.y-bb.y);
}
int n,m,sig,cnt,tot,cont;
void add(int x,int y){vc[x].push_back(y);
}
void top(){memset(pt,0,sizeof(pt));queue<int>s;for(int i=1;i<=sig;i++){if(deg[i]==0) s.push(i);}while(!s.empty()){int u=s.front();if(pt[u]==0){pt[u]=1;pt[pos[u]]=2;}s.pop();for(int i=0;i<vc2[u].size();i++){int v=vc2[u][i];deg[v]--;if(deg[v]==0) s.push(v);}}cont=0;for(int i=1;i<=n;i++) {if(pt[color[i]]==1) op[cont++]=i;}
}
void tarjan(int u)
{vis[u]=1;dfn[u]=low[u]=cnt++;stk[++tot]=u;for(int i=0;i<vc[u].size();i++){int v=vc[u][i];if(vis[v]==0) tarjan(v);if(vis[v]==1) low[u]=min(low[u],low[v]);}if(low[u]==dfn[u]) {sig++;do{vis[stk[tot]]=-1;color[stk[tot]]=sig;}while(stk[tot--]!=u);}
}
void init(){sig=0;cnt=1;tot=-1;memset(deg,0,sizeof(deg));memset(stk,0,sizeof(stk));memset(dfn,0,sizeof(dfn));memset(vis,0,sizeof(vis));memset(color,0,sizeof(color));for(int i=0;i<maxn;i++) {vc[i].clear();vc2[i].clear();}
}
int solve(){for(int i=1;i<=m*2;i++) {if(vis[i]==0) tarjan(i);}for(int i=1;i<=m;i++) {if(color[i]==color[i+m]) return 0;pos[color[i]]=color[i+m];pos[color[i+m]]=color[i];}for(int i=1;i<=m*2;i++){for(int j=0;j<vc[i].size();j++){int v=vc[i][j];if(color[i]!=color[v]){deg[color[i]]++;vc2[color[v]].push_back(color[i]);}}}top();return 1;
}
bool judge(int mid)
{init();for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){if(dis[i]+dis[j]>mid){add(i,j+n);add(j,i+n);}if(dis[i+n]+dis[j+n]>mid){add(i+n,j);add(j+n,i);}if(dis[i]+slen+dis[j+n]>mid){add(i,j);add(j+n,i+n);}if(dis[i+n]+slen+dis[j]>mid){add(i+n,j+n);add(j,i);}}}for(int i=0;i<a;i++){add(hate[i].x,hate[i].y+n);add(hate[i].y+n,hate[i].x);add(hate[i].x+n,hate[i].y);add(hate[i].y,hate[i].x+n);}for(int i=0;i<b;i++){add(like[i].x,like[i].y);add(like[i].y,like[i].x);add(like[i].x+n,like[i].y+n);add(like[i].y+n,like[i].x+n);}return solve();
}
int main()
{scanf("%d%d",&n,&m);init();for(int i=1;i<=m;i++){scanf("%d%d",&x[i],&y[i]);x[i]++;y[i]++;if(x[i]>y[i])swap(x[i],y[i]);}for(int i=1;i<=m;i++)for(int j=i+1;j<=m;j++)if((x[i]<=x[j]&&y[i]>=x[j]&&y[i]<=y[j])||(x[i]>=x[j]&&x[i]<=y[j]&&y[i]>=y[j])){add(i,j+m);add(j,i+m);add(i+m,j);add(j+m,i);}int ans=solve();if(ans)printf("panda is telling the truth...\n");else printf("the evil panda is lying again\n");return 0;
}