AOJ : 1226 - Fishnet

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1226

1*1の正方形の各辺に、ｎ個ずつ点が打たれます。
この点を、反対側の辺に打たれた点と結び、問題文中の図のように線分を引きます。
このとき、正方形がいくつかの四角形に分断されるので、それらの四角形の中で一番大きい面積を答えるのがこの問題です。

アルゴリズム

まず、線分と線分のすべての交点の座標を求めます。
あとは、四角形の左上・右上・右下・左下になる点を二重ループで決めて面積を計算し、最大の面積を求めるだけです。
アジア地区にしては、結構簡単なレベルの幾何です。

プログラム

#include <iostream>
#include <cstdio>
#include <complex>
#include <vector>
using namespace std;

typedef complex<double> P;

#define REP(i,n,m) for(int i=n;i<m;i++)
#define rep(i,n) REP(i,0,n)

double area(vector<P> p){
  int n = p.size();
  double res = 0.0;

  rep(i,n){
    res += p[i].real() * p[(i+1)%n].imag() - p[(i+1)%n].real() * p[i].imag();
  }
  return fabs(res/2);
}

double cross(P a, P b){
  return (a.real() * b.imag() - a.imag() * b.real());
}

P intersection_l(P a1, P a2, P b1, P b2){
  P a = a2 - a1;
  P b = b2 - b1;
  return a1 + a * cross(b, b1-a1) / cross(b, a);
}

int main(void){
  int n;

  while(cin>>n && n){
    P v[n+2][n+2];

    v[0][0] = P(0,0);
    v[0][n+1] = P(1,0);
    v[n+1][0] = P(0,1);
    v[n+1][n+1] = P(1,1);

    REP(i,1,n+1) { v[0][i].imag() = 0;   cin>>v[0][i].real(); }
    REP(i,1,n+1) { v[n+1][i].imag() = 1; cin>>v[n+1][i].real(); }
    REP(i,1,n+1) { v[i][0].real() = 0;   cin>>v[i][0].imag(); }
    REP(i,1,n+1) { v[i][n+1].real() = 1; cin>>v[i][n+1].imag(); }

    REP(i,1,n+1){
      REP(j,1,n+1){
        v[i][j] = intersection_l(v[0][j],v[n+1][j],v[i][0],v[i][n+1]);
      }
    }

    double ans = 0.0;
    rep(i,n+1){
      rep(j,n+1){
        vector<P> p;
        p.push_back(v[i][j]);
        p.push_back(v[i+1][j]);
        p.push_back(v[i+1][j+1]);
        p.push_back(v[i][j+1]);
        ans = max(ans,area(p));
      }
    }
    printf("%.6lf\n",ans);
  }

  return 0;
}