以后绝对要记得 标记的数组要用 bool型！！
之前用int型的超时 而改成bool型的居然就过了
判断一个图形是否是凸多边形 只要看里面是不是有一个角是>180度的就行了
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; double x[20000],y[20000]; bool vis[40][40][40][40]; int is(int i,int j,int k) { double ax=x[j]-x[i]; double ay=y[j]-y[i]; double bx=x[k]-x[j]; double by=y[k]-y[j]; double cross; cross=ax*by-bx*ay; if(cross+0.000001<0) return 1; return 0; } int ok(int i,int j,int k,int w) { if(i==j||i==k||i==w||j==k||j==w||k==w) return 1; if(is(i,j,k)||is(j,k,w)||is(k,w,i)||is(w,i,j)) return 1; return 0; } int main() { int i,j,k,w,n,m,ppp=1,t; int num; scanf("%d",&t); while(t--) { num=0; memset(vis,false,sizeof(vis)); scanf("%d",&n); for(i=0;i<n;i++) scanf("%lf%lf",&x[i],&y[i]); for(i=0;i<n;i++) for(j=0;j<n;j++)if(i!=j) for(k=0;k<n;k++)if(k!=j&&k!=i) for(w=0;w<n;w++)if(w!=k&&w!=i&&w!=j) { if(!vis[i][j][k][w]&&!ok(i,j,k,w)) { vis[i][j][k][w]=true; vis[i][j][w][k]=true; vis[i][k][j][w]=true; vis[i][k][w][j]=true; vis[i][w][j][k]=true; vis[i][w][k][j]=true; vis[j][i][k][w]=vis[j][i][w][k]=vis[j][k][i][w]=vis[j][k][w][i]=vis[j][w][i][k]=vis[j][w][k][i]=true; vis[k][i][j][w]=vis[k][i][w][j]=vis[k][j][i][k]=vis[k][j][k][i]=vis[k][w][i][j]=vis[k][w][j][i]=true; vis[w][i][j][k]=vis[w][i][k][j]=vis[w][j][i][k]=vis[w][j][k][i]=vis[w][k][i][j]=vis[w][k][j][i]=true; num++; } } printf("Case %d: %d ",ppp++,num); } return 0; }