乱搞一下，可以推出如果相交，必定是这条边之前的8条内的一条，那么对于每条边，暴力判断一下。
就可以得出答案了，复杂度是O(跑的过)。
#include <Cstdio> #include <algorithm> #define C (c=getchar()) using namespace std; int T; inline void read(int &a) { a=0;static char c;C; while (c<'0'||c>'9') C; while (c>='0'&&c<='9') a=a*10+c-'0',C; } int f[6][6]; struct whe{ int x,y; }p[1000005]; struct ee{ int u,v,flag; }e[1000005]; int tot; inline bool work(int x) { int k=0; int f1=f[e[x].flag][1],f2=f[e[x].flag][2]; int x1=p[e[x].u].x,y1=p[e[x].u].y,x2=p[e[x].v].x,y2=p[e[x].v].y; for (int i=x-2;i>=1&&k<=4;i--) { if (e[i].flag==f1||e[i].flag==f2) { int x3=p[e[i].u].x,y3=p[e[i].u].y,x4=p[e[i].v].x,y4=p[e[i].v].y; if (x3==x4) { if (e[x].flag==2) if (x2>=x3&&x1<=x3&&y2>=min(y3,y4)&&y2<=max(y3,y4)) return 1; if (e[x].flag==4) if (x2<=x3&&x1>=x3&&y2>=min(y3,y4)&&y2<=max(y3,y4)) return 1; } if (y3==y4) { if (e[x].flag==1) if (y2>=y3&&y1<=y3&&x2>=min(x3,x4)&&x2<=max(x3,x4)) return 1; if (e[x].flag==3) if (y2<=y3&&y1>=y3&&x2>=min(x3,x4)&&x2<=max(x3,x4)) return 1; } k++; } } return 0; } int main() { register int i,j,k; read(T); f[1][1]=f[3][1]=2; f[1][2]=f[3][2]=4; f[2][1]=f[4][1]=1; f[2][2]=f[4][2]=3; for (k=1;k<=T;k++) { int flag=1; tot=1; int n,x=0,y=0,t; read(n); for (i=1;i<=n;i++) { read(t); if (flag==5) continue; if (flag==1) { e[tot].flag=flag; flag++; y+=t; p[i].x=x; p[i].y=y; e[tot].u=i-1;e[tot].v=i; if (tot>3&&work(tot)) { printf("%d\n",i); flag=5; } tot++; continue; } if (flag==2) { e[tot].flag=flag; flag++; x+=t; p[i].x=x; p[i].y=y; e[tot].u=i-1;e[tot].v=i; if (tot>3&&work(tot)) { printf("%d\n",i); flag=5; } tot++; continue; } if (flag==3) { e[tot].flag=flag; flag++; y-=t; p[i].x=x; p[i].y=y; e[tot].u=i-1;e[tot].v=i; if (tot>3&&work(tot)) { printf("%d\n",i); flag=5; } tot++; continue; } if (flag==4) { e[tot].flag=flag; flag=1; x-=t; p[i].x=x; p[i].y=y; e[tot].u=i-1;e[tot].v=i; if (tot>3&&work(tot)) { printf("%d\n",i); flag=5; } tot++; continue; } } if (flag!=5) printf("Catch you\n"); } return 0; }