PKU 1408 Fishnet

http://poj.org/problem?id=1408
1*1を四角形に区切る。
一番大きな面積のマスの大きさを答えろというような問題。

幾何。
以下のページをパクって参考にして直線の交点を求めて、面積の最大値を計算しました。式変形での交点計算は式を書いている途中で心が折れました。
http://imagingsolution.blog107.fc2.com/blog-entry-137.html

typedef pair<double,double> PD;

PD operator-(const PD&a,const PD&b){
  return mp(a.F-b.F,a.S-b.S);
}

double dotP(const PD&a,const PD&b){
  return a.F*b.S-a.S*b.F;
}

double in[4][100];

double *a,*b,*c,*d;
int n;

PD po[40][40];

PD crossP(PD a,PD b,PD c,PD d){
  double s1=dotP(d-c,a-c)/2;
  double s2=dotP(d-c,c-b)/2;

  return mp(a.F+(b.F-a.F)*s1/(s1+s2),
            a.S+(b.S-a.S)*s1/(s1+s2));
}

double area(const PD&a,const PD&b,const PD&c,const PD&d){
  return abs(dotP(b-a,d-a))/2+abs(dotP(b-c,d-c))/2;
}

void solve(){
  rep(i,4)rep(j,n)cin>>in[i][j];
  a=in[0];
  b=in[1];
  c=in[2];
  d=in[3];
  
  po[0][0]=mp(0,0);
  rep(i,n)po[i+1][0]=mp(a[i],0);
  po[n+1][0]=mp(1,0);
  rep(i,n){
    po[0][i+1]=mp(0,c[i]);
    rep(j,n)
      po[j+1][i+1]=crossP(mp(0,c[i]),mp(1,d[i]),
                          mp(a[j],0),mp(b[j],1));
    po[n+1][i+1]=mp(1,d[i]);
  }
  po[0][n+1]=mp(0,1);
  rep(i,n)po[i+1][n+1]=mp(b[i],1);
  po[n+1][n+1]=mp(1,1);

  double ans=0;
  rep(i,n+1)rep(j,n+1)
    ans=max(ans,
            area(po[i][j],po[i+1][j],po[i+1][j+1],po[i][j+1]));
  printf("%.6f\n",ans);
}

main(){
  while(cin>>n,n)solve();
}