题意:给出一个圆,圆上有许多点,点与点之间有连线,连线要么在圆内,要么在圆外。现在给出所有连线的两个端点,判断这些线能否不相交?
#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> using namespace std; const int SIZE = 5010; int n, m; int e[SIZE][2]; int head[SIZE], E; bool instk[SIZE]; int stk[SIZE], top; int blk[SIZE], blkCnt; int low[SIZE], dfn[SIZE], tim; struct EDGE { int v, next; } edge[SIZE*100]; void init() { E = top = blkCnt = tim = 0; for(int i = 0; i < m + m; i++) { head[i] = blk[i] = low[i] = dfn[i] = -1; instk[i] = false; } } void add(int u, int v) { edge[E].v = v; edge[E].next = head[u]; head[u] = E++; } bool touch(int i, int j) { if((e[i][0] <= e[j][0] && e[i][1] >= e[j][0] && e[i][1] <= e[j][1]) || (e[i][0] >= e[j][0] && e[i][0] <= e[j][1] && e[i][1] >= e[j][1])) return true; return false; } void tarjan(int u) { int v; instk[u] = true; stk[top++] = u; low[u] = dfn[u] = tim++; for(int i = head[u]; i != -1; i = edge[i].next) { v = edge[i].v; if(dfn[v] == -1) { tarjan(v); low[u] = min(low[u], low[v]); } else if(instk[v]) low[u] = min(low[u], dfn[v]); } if(low[u] == dfn[u]) { if(top == -1 || top == 0) return; do { v = stk[top-1]; top--; instk[v] = false; blk[v] = blkCnt; } while(v != u); blkCnt++; } } int main() { scanf("%d%d",&n,&m); int i, j; for(i = 0; i < m; i++) { scanf("%d%d",&e[i][0], &e[i][1]); if(e[i][0] > e[i][1]) swap(e[i][0], e[i][1]); } init(); for(i = 0; i < m; i++) for(j = i + 1; j < m; j++) if(touch(i, j)) { add(i, j+m); add(i+m, j); add(j, i+m); add(j+m, i); } for(i = 0; i < m + m; i++) if(dfn[i] == -1) tarjan(i); for(i = 0; i < m; i++) if(blk[i] == blk[i+m]) break; if(i == m) printf("panda is telling the truth...\n"); else printf("the evil panda is lying again\n"); return 0; }