構造所有的線段，然后枚舉每對水平－豎直線段，求交點，然后計算四邊形面積，求最大值。
/**//*************************************************************************
Author: WHU_GCC
Created Time: 2007-9-25 20:39:43
File Name: pku1408.cpp
Description:
************************************************************************/
#include <iostream>
#include <cmath>
using namespace std;
typedef long long int64;
const int maxint = 0x7FFFFFFF;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
const double eps = 1E-9;
const double pi = acos(-1.0);
const double inf = 1E200;
#define out(x) (cout<<#x<<": "<<x<<endl)
template <class T> void show(T a, int n) 
{for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl;}
template <class T> void show(T a, int r, int l) {for (int i = 0; i < r; ++i) show(a[i],l); cout << endl;}
/**//********************
基本幾何結構
點
線段
直線
多邊形
圓
********************/
// 點, 同時也可以看成向量
struct point_t
{
double x, y;
point_t(double a = 0, double b = 0)
{
x = a;
y = b;
}
};
// 線段
struct lineseg_t
{
point_t s, e;
lineseg_t()
{
}
lineseg_t(point_t a, point_t b)
{
s = a;
e = b;
}
};
// 直線
// 解析方程 ax + by + c = 0 為統一表示，約定 a >= 0
struct line_t
{
double a, b, c;
line_t(double d1 = 1, double d2 = -1, double d3 = 0)
{
a = d1;
b = d2;
c = d3;
}
};
// 這里定義多邊形的最大點數
const int max_polygon_size = 1000;
// 多邊形, 規定逆時針為正方向
struct polygon_t
{
int n;
point_t p[max_polygon_size];
};
// 圓
struct circle_t
{
point_t center;
double r;
};
/**//********************
常用小函數與算符
浮點數比較
平方
點到原點距離
兩點距離
兩點重合
********************/
// 浮點數與0比較. x == 0 返回 0, x > 0 返回 1, x < 0 返回 -1
int dcmp(double x)
{
if (-eps < x && x < eps)
return 0;
else if (x > 0)
return 1;
else
return -1;
}
// 判斷兩個點是否重合
bool operator ==(const point_t &a, const point_t &b)
{
return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0;
}
bool operator !=(const point_t &a, const point_t &b)
{
return !(a == b);
}
// 向量加法
point_t operator +(const point_t &a, const point_t &b)
{
point_t ret(a.x + b.x, a.y + b.y);
return ret;
}
// 向量減法
point_t operator -(const point_t &a, const point_t &b)
{
point_t ret(a.x - b.x, a.y - b.y);
return ret;
}
// 平方
inline double sqr(double x)
{
return x * x;
}
// 點到原點距離
double dist(const point_t &p)
{
return sqrt(sqr(p.x) + sqr(p.y));
}
// 兩點距離
double dist(const point_t &a, const point_t &b)
{
return sqrt(dist(a - b));
}
/**//********************\
* *
* 點的基本運算 *
* *
\********************/
/**//******************************************************************************
r=multiply(sp,ep,op),得到(sp-op)*(ep-op)的叉積
r>0:ep在矢量opsp的逆時針方向；
r=0：opspep三點共線；
r<0:ep在矢量opsp的順時針方向
*******************************************************************************/
double cross_mul(const point_t &a, const point_t &b)
{
return a.x * b.y - a.y * b.x;
}
double dot_mul(const point_t &a, const point_t &b)
{
return a.x * b.x + a.y * b.y;
}
double cross_mul(const point_t &a, const point_t &b, const point_t &c)
{
return cross_mul(a - c, b - c);
}
/**//*******************************************************************************
r=dotmultiply(p1,p2,op),得到矢量(p1-op)和(p2-op)的點積，如果兩個矢量都非零矢量
r<0:兩矢量夾角為銳角；r=0：兩矢量夾角為直角；r>0:兩矢量夾角為鈍角
*******************************************************************************/
double dot_mul(const point_t &a, const point_t &b, const point_t &c)
{
return dot_mul(a - c, b - c);
}
// 判斷點p是否在線段l上
// 條件：p在線段l所在的直線上 && 點p在以線段l為對角線的矩形內
bool online(const lineseg_t l, const point_t p)
{
return dcmp(cross_mul(l.e, p, l.s)) == 0 && (p.x - l.s.x) * (p.x - l.e.x) <= 0 && (p.y - l.s.y) * (p.y - l.e.y) <= 0;
}
// 返回點p以點o為圓心逆時針旋轉alpha(單位：弧度)后所在的位置
point_t rotate(const point_t &o, double alpha, point_t p)
{
point_t ret;
p.x -= o.x;
p.y -= o.y;
ret.x = p.x * cos(alpha) - p.y * sin(alpha) + o.x;
ret.y = p.y * cos(alpha) + p.x * sin(alpha) + o.y;
return ret;
}
// 返回向量a按逆時針方向,旋轉到向量b的角度
// 角度小于pi，返回正值
// 角度大于pi，返回負值
double angle(const point_t &a, const point_t &b)
{
double ret = acos(dot_mul(a, b) / (dist(a) * dist(b)));
if (cross_mul(a, b) < 0)
return ret;
else
return -ret;
}
// 返回頂角在o點,起始邊為os,終止邊為oe的夾角(單位:弧度),規定逆時針為正方向
// 角度小于pi，返回正值
// 角度大于pi，返回負值
// 可以用于求線段之間的夾角
double angle(const point_t &o, const point_t &s, const point_t &e)
{
return angle(s - o, e - o);
}
// 線段及直線的基本運算
/**//* 判斷點與線段的關系,用途很廣泛
本函數是根據下面的公式寫的,P是點C到線段AB所在直線的垂足
AC dot AB
r = ---------
||AB||^2
(Cx-Ax)(Bx-Ax) + (Cy-Ay)(By-Ay)
= -------------------------------
L^2
r has the following meaning:
r=0 P = A
r=1 P = B
r<0 P is on the backward extension of AB
r>1 P is on the forward extension of AB
0<r<1 P is interior to AB
*/
double relation(const point_t &p, const lineseg_t &l)
{
return dot_mul(p, l.e, l.s) / (dist(l.s, l.e) * dist(l.s, l.e));
}
// 求點p到線段l所在直線的垂足
point_t foot(const point_t &p, const lineseg_t &l)
{
double r = relation(p, l);
point_t ret;
ret.x = l.s.x + r * (l.e.x - l.s.x);
ret.y = l.s.y + r * (l.e.y - l.s.y);
return ret;
}
// 求點p到線段l的最短距離,并返回線段上距該點最近的點ret
// 注意: ret是線段l上到點p最近的點,不一定是垂足
double dist(const point_t p, const lineseg_t &l, point_t &ret)
{
double r = relation(p,l);
if (r < 0)
ret = l.s;
else if (r > 1)
ret = l.e;
else
ret = foot(p,l);
return dist(p, ret);
}
// 求點p到線段l所在直線的距離,請注意本函數與上個函數的區別
double dist(const point_t p, const lineseg_t l)
{
return abs(cross_mul(p, l.e, l.s)) / dist(l.s, l.e);
}
// 計算點到折線集的最近距離,并返回最近點
double dist(int cnt_v, point_t point_set[], const point_t &p, point_t &ret_p)
{
double ret = inf;
for (int i = 0; i < cnt_v - 1; i++)
{
lineseg_t l(point_set[i], point_set[i + 1]);
point_t tmp_p;
double tmp = dist(p, l, tmp_p);
if (tmp < ret)
{
ret = tmp;
ret_p = tmp_p;
}
}
return ret;
}
// 判斷圓是否在多邊形內
bool inside(const circle_t c, int cnt_v, point_t poly[])
{
point_t q;
double d = dist(cnt_v, poly, c.center, q);
return d < c.r || fabs(d - c.r) < eps;
}
// 如果線段a和b相交(包括相交在端點處)時返回true
bool intersect_e(const lineseg_t &a, const lineseg_t &b)
{
return
//排斥實驗
max(a.s.x, a.e.x) >= min(b.s.x, b.e.x) &&
max(b.s.x, b.e.x) >= min(a.s.x, a.e.x) &&
max(a.s.y, a.e.y) >= min(b.s.y, b.e.y) &&
max(b.s.y, b.e.y) >= min(a.s.y, a.e.y) &&
//跨立實驗
cross_mul(b.s, a.e, a.s) * cross_mul(a.e, b.e, a.s) >= 0 &&
cross_mul(a.s, b.e, b.s) * cross_mul(b.e, a.e, b.s) >= 0;
}
// 線段a和b相交 && 交點不是雙方的端點時返回true
bool intersect_ne(const lineseg_t &a, const lineseg_t &b)
{
return
intersect_e(a, b) &&
!online(a, b.s) &&
!online(a, b.e) &&
!online(b, a.e) &&
!online(b, a.s);
}
// 線段l所在直線與線段a相交(包括相交在端點處)時返回true
// 方法:判斷線段a是否跨立線段l
bool intersect_l(const lineseg_t &a, const lineseg_t &l)
{
return cross_mul(a.s, l.e, l.s) * cross_mul(l.e, a.e, l.s) >= 0;
}
// 根據已知兩點坐標,求過這兩點的直線解析方程: ax + by + c = 0 (a >= 0)
// 若兩點不重合,返回true,否則返回false
bool make_line(const point_t &a, const point_t &b, line_t &ret)
{
int sign = 1;
ret.a = b.y - a.y;
if (dcmp(ret.a) == 0 && dcmp(b.x - a.x) == 0)
return false;
if (dcmp(ret.a) == 0)
{
ret.a = 0;
ret.b = 1;
ret.c = -a.y;
return true;
}
if (ret.a < 0)
{
sign = -1;
ret.a = -ret.a;
}
ret.b = sign * (a.x - b.x);
ret.c = sign * (a.y * b.x - a.x * b.y);
return true;
}
// 根據直線解析方程返回直線的斜率k,水平線返回0,豎直線返回inf
double slope(const line_t &l)
{
if (dcmp(l.a) == 0)
return 0;
if (dcmp(l.b) == 0)
return inf;
return -(l.a / l.b);
}
// 返回直線的傾斜角alpha (0 - pi)
double alpha(const line_t &l)
{
if (dcmp(l.a) == 0)
return 0;
if (dcmp(l.b) == 0)
return pi / 2;
double k = slope(l);
return k > 0 ? atan(k) : pi + atan(k);
}
// 求點p關于直線l的對稱點
point_t symmetry(const line_t &l, const point_t &p)
{
point_t ret;
double sla = sqr(l.a), slb = sqr(l.b);
ret.x = ((slb - sla) * p.x - 2 * l.a * l.b * p.y - 2 * l.a * l.c) / (sla + slb);
ret.y = ((sla - slb) * p.y - 2 * l.a * l.b * p.x - 2 * l.b * l.c) / (sla + slb);
return ret;
}
// 如果兩條直線 l1(a1x + b1y + c1 = 0), l2(a2x + b2y + c2 = 0)相交, 返回true, 且返回交點p
bool intersect(const line_t &l1, const line_t &l2, point_t &p)
{
double d = l1.a * l2.b - l2.a * l1.b;
if (dcmp(d) == 0)
return false;
p.x = (l2.c * l1.b - l1.c * l2.b) / d;
p.y = (l2.a * l1.c - l1.a * l2.c) / d;
return true;
}
// 如果線段l1和l2相交，返回true且交點由(inter)返回，否則返回false
bool intersect(const lineseg_t &l1, const lineseg_t &l2, point_t &ret)
{
line_t t1, t2;
make_line(l1.s, l1.e, t1);
make_line(l2.s, l2.e, t2);
if (intersect(t1, t2, ret))
return online(l1, ret) && online(l2, ret);
else
return false;
}
//點到直線距離
double dist(const point_t &a, const line_t &b)
{
return abs(b.a * a.x + b.b * a.y + b.c) / sqrt(sqr(b.a) + sqr(b.b));
}
double area(point_t a, point_t b, point_t c, point_t d)
{
return abs(cross_mul(a, b) + cross_mul(b, c) + cross_mul(c, d) + cross_mul(d, a));
}
const int maxn = 40;
int n;
lineseg_t ls_h[maxn], ls_v[maxn];
point_t p[maxn][maxn];
int main()
{
double tmp1[maxn], tmp2[maxn];
while (scanf("%d", &n), n != 0)
{
tmp1[0] = 0;
tmp2[0] = 0;
tmp1[n + 1] = 1;
tmp2[n + 1] = 1;
for (int i = 1; i <= n; i++)
scanf("%lf", &tmp1[i]);
for (int i = 1; i <= n; i++)
scanf("%lf", &tmp2[i]);
for (int i = 0; i <= n + 1; i++)
{
point_t t1(tmp1[i], 0);
point_t t2(tmp2[i], 1);
lineseg_t tt1(t1, t2);
ls_v[i] = tt1;
}
tmp1[0] = 0;
tmp2[0] = 0;
tmp1[n + 1] = 1;
tmp2[n + 1] = 1;
for (int i = 1; i <= n; i++)
scanf("%lf", &tmp1[i]);
for (int i = 1; i <= n; i++)
scanf("%lf", &tmp2[i]);
for (int i = 0; i <= n + 1; i++)
{
point_t t1(0, tmp1[i]);
point_t t2(1, tmp2[i]);
lineseg_t tt1(t1, t2);
ls_h[i] = tt1;
}
for (int i = 0; i <= n + 1; i++)
for (int j = 0; j <= n + 1; j++)
{
intersect(ls_v[i], ls_h[j], p[i][j]);
}
double ans = -1;
for (int i = 0; i <= n; i++)
for (int j = 0; j <= n; j++)
ans >?= area(p[i][j], p[i + 1][j], p[i + 1][j + 1], p[i][j + 1]);
printf("%lf\n", ans / 2);
}
return 0;
}