1408.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
#include"math.h"
#include"stdio.h"
double d[32][32][2];

inline void dian(double x1,double x2,double y1,double y2,double a[2])
{double k1,k2,b1,b2;
if(x1==x2){a[0]=x1;a[1]=y1+(y2-y1)*x1;return;}
if(y1==y2){a[1]=y1;a[0]=x1+(x2-x1)*y1;return;}
k1=y2-y1;k2=1/(x2-x1);
b1=y1;
b2=1/(x1-x2)*x1;
a[0]=(b2-b1)/(k1-k2);
a[1]=a[0]*k1+b1;
return;
}

inline double mj(int i,int j)
{double s=0,
x1=d[i][j+1][0]-d[i][j][0],
y1=d[i][j+1][1]-d[i][j][1],
x2=d[i+1][j+1][0]-d[i][j][0],
y2=d[i+1][j+1][1]-d[i][j][1],
x3=d[i+1][j][0]-d[i][j][0],
y3=d[i+1][j][1]-d[i][j][1];

s=fabs(x1*y2-x2*y1)+fabs(x2*y3-x3*y2);
s*=0.5;
return s;
}

int main()
{int n,i,j,k;double s,big;
while(1)
{cin>>n;if(n==0)break;

for(i=1;i<=n;i++)
{cin>>d[i][0][0];d[i][0][1]=0;}
for(i=1;i<=n;i++)
{cin>>d[i][n+1][0];d[i][n+1][1]=1;}

for(i=1;i<=n;i++)
{cin>>d[0][i][1];d[0][i][0]=0;}
for(i=1;i<=n;i++)
{cin>>d[n+1][i][1];d[n+1][i][0]=1;}


d[0][0][0]=0;d[0][0][1]=0;
d[n+1][n+1][0]=1;d[n+1][n+1][1]=1;
d[0][n+1][0]=0;d[0][n+1][1]=1;
d[n+1][0][0]=1;d[n+1][0][1]=0;

for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
dian(d[i][0][0],d[i][n+1][0],d[0][j][1],d[n+1][j][1],d[i][j]);

big=0;




for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
if((s=mj(i,j))>big)big=s;

printf("%.6f\n",big);
}
return 1;
}