题目来源：

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;
}