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