ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 1226 Fishnet

・概要
問題文はこちら
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1226

正方形を何本かの線分で分割されたとき、その中で最大の面積を求める問題です。


・解法
幾何問題です(線分と線分の交点を求める、面積の計算など)

線分と線分の交点やpegの座標を全て配列に入れます。
元の正方形の4点((0,0), (0,1), (1,0), (1,1))も入れます。

あとは外積を用いて面積を計算すればよいです。


ソースコード
ライブラリは省略

#include<iostream>
#include<algorithm>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<vector>
#include<complex>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<cstring>
#include<cassert>
using namespace std;
 
#define REP(i,x,n) for(int i = x ; i < (int)(n) ; i++)
#define rep(i,n) REP(i, 0, n)
 
typedef pair<int,int> P;
typedef long long ll;
 
static const int INF = (1<<29);
static const double EPS = 1e-9;
static const double PI = acos(-1.0);
typedef complex<double> Point;
typedef vector<Point> Polygon;
 
struct Segment{
  Point p1,p2;
  Segment(){}
  Segment(Point p1, Point p2):p1(p1),p2(p2){}
};

double area(Polygon p){
  double S = 0;
  for(int i = 0 ; i < p.size() ; i++){
    S += cross(p[i], p[(i+1)%p.size()]);
  }
  return fabs(S/2.0);
}

int n;
Point point[32][32];
Point peg[4][30]; //a,b,c,d
 
double solve(){
  point[0][0] = Point(0,0);
  point[0][n+1] = Point(0,1);
  point[n+1][0] = Point(1,0);
  point[n+1][n+1] = Point(1,1);
   
  rep(j,n) point[0][j+1] = peg[0][j];
  rep(j,n) point[n+1][j+1] = peg[1][j];
   
  rep(i,n){//c,d
    point[i+1][0] = peg[2][i];
    point[i+1][n+1] = peg[3][i];
    Segment cd = Segment(peg[2][i],peg[3][i]);
    rep(j,n){//a,b
      Segment ab = Segment(peg[0][j],peg[1][j]);
      Point pp = getCrossPoint(ab,cd);
      point[i+1][j+1] = pp;
    }
  }
  
  double ans = 0;
  for(int i = 1 ; i < n+2 ; i++){
    for(int j = 1 ; j < n+2 ; j++){
      Polygon poly(4);
      poly[0] = point[i-1][j-1];
      poly[1] = point[i][j-1];
      poly[2] = point[i][j];
      poly[3] = point[i-1][j];
      ans = max(ans,area(poly));
    }
  }
  return ans;
}
 
int main(){
  while(cin >> n, n){
    rep(i,4){
      rep(j,n){
        double x,y,tmp;
        cin >> tmp;
        if(i==0){x = 0; y = tmp;}
        if(i==1){x = 1; y = tmp;}
        if(i==2){x = tmp; y = 0;}
        if(i==3){x = tmp; y = 1;}
        peg[i][j] = Point(x,y);
      }
    }
    printf("%.10f\n",solve());
  }
  return 0;
}