声明：以下代码可能有很多错误，请楼主先测一下，最好能把所有测试数据给我。
MY QQ:652951917
#include<stdio.h>
#include<math.h>
typedef struct xian
{
float k,b;
bool s,a;
}XIAN;
float S(float a,float b,float c)
{
float p;
p=(a+b+c)/2;
return(sqrt(p*(p-a)*(p-b)*(p-c)));
}
int main()
{
int n,mi[10],dian[10][50][2],i,j,k,ce,mid;
float x,y,x1,x2,y1,y2,t,ch[2][250][2],px[250],fin[50][50],result=0.0;
XIAN D[10][50],temp[250];
FILE *fp,*fpt;
fp=fopen(".\\polygon.in","r");
fscanf(fp,"%d",&n);
for(i=0;i<n;i++)
{
fscanf(fp,"%d",&mi);
for(j=0;j<mi;j++) fscanf(fp,"%d%d",&dian[j][0],&dian[j][1]);
dian[j][0]=dian[0][0];
dian[j][1]=dian[0][1];
dian[j+1][0]=dian[1][0];
dian[j+1][1]=dian[1][1];
for(j=0;j<mi;j++)
{
if(dian[j][0]==dian[j+1][0])
{
D[j].a=0;
D[j].b=dian[j][0];
if(dian[j+2][0]>D[j].b) D[j].s=1; //图在线左
else D[j].s=0;
}
else
{
D[j].a=1;
D[j].k=(float)(dian[j][1]-dian[j+1][1])/(dian[j][0]-dian[j+1][0]);
D[j].b=(float)dian[j][1]-D[j].k*dian[j][0];
if(D[j].k*dian[j+2][0]+D[j].b>dian[j+2][1]) D[j].s=0; //图在线下
else D[j].s=1;
}
}
}
fclose(fp);
for(i=1;i<=mi[0];i++) {ch[0][0]=dian[0][i-1][0]; ch[0][1]=dian[0][i-1][1];}
ch[0][0][0]=mi[0];
for(i=1;i<n;i++)
{
ch[(i+1)%2][(int)ch[(i+1)%2][0][0]+1][0]=ch[(i+1)%2][1][0];
ch[(i+1)%2][(int)ch[(i+1)%2][0][0]+1][1]=ch[(i+1)%2][1][1];
ch[(i+1)%2][(int)ch[(i+1)%2][0][0]+2][0]=ch[(i+1)%2][2][0];
ch[(i+1)%2][(int)ch[(i+1)%2][0][0]+2][1]=ch[(i+1)%2][2][1];
for(j=1;j<=ch[(i+1)%2][0][0];j++)
{
if(ch[(i+1)%2][j][0]==ch[(i+1)%2][j+1][0])
{
temp[j].a=0;
temp[j].b=ch[(i+1)%2][j][0];
if(ch[(i+1)%2][j+2][0]>temp[j].b) temp[j].s=1;
else temp[j].s=0;
}
else
{
temp[j].a=1;
temp[j].k=(float)(ch[(i+1)%2][j][1]-ch[(i+1)%2][j+1][1])/(ch[(i+1)%2][j][0]-ch[(i+1)%2][j+1][0]);
temp[j].b=(float)ch[(i+1)%2][j][1]-temp[j].k*ch[(i+1)%2][j][0];
if(temp[j].k*ch[(i+1)%2][j+2][0]+temp[j].b>ch[(i+1)%2][j+2][1]) temp[j].s=0; //图在线下
else temp[j].s=1;
}
}
ch[i%2][0][0]=1;
for(j=0;j<mi;j++)
{
for(k=1;k<=ch[(i+1)%2][0][0];k++)
{
if(D[j].a==0)
{
x=D[j].b;
y=x*temp[k].k+temp[k].b;
}
else if(temp[k].a==0)
{
x=temp[k].b;
y=x*D[j].k+D[j].b;
}
else
{
x=(D[j].b-temp[k].b)/(temp[k].k-D[j].k);
y=x*D[j].k+D[j].b;
}
x1=dian[j][0];
x2=dian[j+1][0];
y1=dian[j][1];
y2=dian[j+1][1];
if(x2<x1) {t=x1; x1=x2; x2=t;}
if(y2<y1) {t=y1; y1=y2; y2=t;}
if(x<=x2&&x>=x1&&y<=y2&&y>=y1)
{
x1=ch[(i+1)%2][k][0];
x2=ch[(i+1)%2][k+1][0];
y1=ch[(i+1)%2][k][1];
y2=ch[(i+1)%2][k+1][1];
if(x2<x1) {t=x1; x1=x2; x2=t;}
if(y2<y1) {t=y1; y1=y2; y2=t;}
if(x<=x2&&x>=x1&&y<=y2&&y>=y1)
{
ch[i%2][(int)ch[i%2][0][0]][0]=x;
ch[i%2][(int)ch[i%2][0][0]++][1]=y;
}
}
}
}
for(j=0;j<mi;j++)
{
for(k=1;k<=ch[(i+1)%2][0][0];k++)
{
if(temp[k].a==0)
{
if(dian[j][0]>temp[k].b) x=1;
else x=0;
if(x!=temp[k].s) break;
}
else
{
if(temp[k].k*dian[j][0]+temp[k].b>dian[j][1]) x=0;
else x=1;
if(x!=temp[k].s) break;
}
}
if(k>ch[(i+1)%2][0][0])
{
ch[i%2][(int)ch[i%2][0][0]][0]=dian[j][0];
ch[i%2][(int)ch[i%2][0][0]++][1]=dian[j][1];
}
}
for(j=1;j<=ch[(i+1)%2][0][0];j++)
{
for(k=0;k<mi;k++)
{
if(D[k].a==0)
{
if(ch[(i+1)%2][j][0]>D[k].b) x=1;
else x=0;
if(x!=D[k].s) break;
}
else
{
if(D[k].k*ch[(i+1)%2][j][0]+D[k].b>ch[(i+1)%2][j][1]) x=0;
else x=1;
if(x!=D[k].s) break;
}
}
if(k>=mi)
{
ch[i%2][(int)ch[i%2][0][0]][0]=ch[(i+1)%2][j][0];
ch[i%2][(int)ch[i%2][0][0]++][1]=ch[(i+1)%2][j][1];
}
}
ch[i%2][0][1]=ch[i%2][(int)ch[i%2][0][0]][1];
ch[i%2][(int)ch[i%2][0][0]][1]=ch[i%2][1][1];
j=1;
for(k=1;k<ch[i%2][0][0];k++)
{
if(ch[i%2][k][0]==0&&(ch[i%2][k][1]>ch[i%2][k-1][1]||ch[i%2][k][1]>ch[i%2][k+1][1]))
{
x=ch[i%2][k][0];
ch[i%2][k][0]=ch[i%2][1][0];
ch[i%2][1][0]=x;
y=ch[i%2][k][1];
ch[i%2][k][1]=ch[i%2][1][1];
ch[i%2][1][1]=y;
px[1]=-999;
j=2;
break;
}
}
ce=-1;
for(;j<ch[i%2][0][0];j++)
{
if(ch[i%2][j][0]>0)
{
for(k=j+1;k<ch[i%2][0][0];k++)
{
if(ch[i%2][k][0]<0)
{
x=ch[i%2][j][0];
ch[i%2][j][0]=ch[i%2][k][0];
ch[i%2][k][0]=x;
y=ch[i%2][j][1];
ch[i%2][j][1]=ch[i%2][k][1];
ch[i%2][k][1]=y;
break;
}
}
if(k>=ch[i%2][0][0]) break;
}
else if(ch[i%2][j][0]==0) ce=j;
}
if(ce!=-1)
{
if(ce>j)
{
x=ch[i%2][j][0];
ch[i%2][j][0]=ch[i%2][ce][0];
ch[i%2][ce][0]=x;
y=ch[i%2][j][1];
ch[i%2][j][1]=ch[i%2][ce][1];
ch[i%2][ce][1]=y;
ce=j-1;
mid=j+1;
}
else if(ce<j)
{
x=ch[i%2][j-1][0];
ch[i%2][j-1][0]=ch[i%2][ce][0];
ch[i%2][ce][0]=x;
y=ch[i%2][j-1][1];
ch[i%2][j-1][1]=ch[i%2][ce][1];
ch[i%2][ce][1]=y;
mid=j;
ce=j-2;
}
}
else {mid=j; ce=--j;}
for(j=1;j<=ch[i%2][0][0];j++)
if(ch[i%2][j][0]!=0)
px[j]=ch[i%2][j][1]/ch[i%2][j][0];
for(j=1;j<=ce;j++)
{
for(k=ce;k>j;k--)
{
if(px[k]<px[k-1])
{
x=ch[i%2][k-1][0];
ch[i%2][k-1][0]=ch[i%2][k][0];
ch[i%2][k][0]=x;
y=ch[i%2][k-1][1];
ch[i%2][k-1][1]=ch[i%2][k][1];
ch[i%2][k][1]=y;
x=px[k];
px[k]=px[k-1];
px[k-1]=x;
}
}
}
for(j=mid;j<ch[i%2][0][0];j++)
{
for(k=(int)ch[i%2][0][0]-1;k>j;k--)
{
if(px[k]<px[k-1])
{
x=ch[i%2][k-1][0];
ch[i%2][k-1][0]=ch[i%2][k][0];
ch[i%2][k][0]=x;
y=ch[i%2][k-1][1];
ch[i%2][k-1][1]=ch[i%2][k][1];
ch[i%2][k][1]=y;
x=px[k];
px[k]=px[k-1];
px[k-1]=x;
}
}
}
}
i=(i+1)%2;
ch[(int)ch[i%2][0][0]][0]=ch[1][0];
ch[(int)ch[i%2][0][0]][1]=ch[1][1];
for(j=1;j<(int)ch[0][0];j++) fin[j][j+1]=fin[j+1][j]=sqrt((ch[j][0]-ch[j+1][0])*(ch[j][0]-ch[j+1][0])+(ch[j][1]-ch[j+1][1])*(ch[j][1]-ch[j+1][1]));
fin[1][j-1]=fin[j-1][1]=fin[j-1][j];
for(j=3;j<(int)ch[0][0]-1;j++) fin[j][1]=fin[1][j]=sqrt((ch[j][0]-ch[1][0])*(ch[j][0]-ch[1][0])+(ch[j][1]-ch[1][1])*(ch[j][1]-ch[1][1]));
for(j=2;j<(int)ch[0][0]-1;j++)
{
fprintf(fpt,"j=%d\n(%f,%f,%f)\ns=%f\n",j,fin[1][j],fin[j][j+1],fin[j+1][1],S(fin[1][j],fin[j][j+1],fin[j+1][1]));
result+=S(fin[1][j],fin[j][j+1],fin[j+1][1]);
}
fp=fopen(".\\polygon.out","w");
fprintf(fp,"%0.3f",result);
fclose(fp);
return 0;
}
