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(); }