求出所有线段的交点，然后利用叉乘求四边形面积即可。
// // main.cpp // poj1408 // // Created by 陈加寿 on 15/12/31. // Copyright (c) 2015年 chenhuan001. All rights reserved. // #include <iostream> #include <cmath> #include <vector> #include <string.h> #include <stdlib.h> #include <algorithm> using namespace std; #define MAX_N 110 /////////////////////////////////////////////////////////////////// //常量区 const double INF = 1e10; // 无穷大 const double EPS = 1e-8; // 计算精度 const double PI = acos(-1.0);// PI const int PINXING = 0; // 平行 const int XIANGJIAO = 1; // 相交 const int XIANGLI = 0; // 相离 const int GONGXIAN = 2; // 共线 const int CHONGDIE = -1; // 重叠 /////////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////// //类型定义区 struct Point { // 二维点或矢量 double x, y; double angle, dis; Point() {} Point(double x0, double y0): x(x0), y(y0) {} }; struct Point3D { //三维点或矢量 double x, y, z; Point3D() {} Point3D(double x0, double y0, double z0): x(x0), y(y0), z(z0) {} }; struct Line { // 二维的直线或线段 Point p1, p2; Line() {} Line(Point p10, Point p20): p1(p10), p2(p20) {} }; struct Line3D { // 三维的直线或线段 Point3D p1, p2; Line3D() {} Line3D(Point3D p10, Point3D p20): p1(p10), p2(p20) {} }; struct Rect { // 用长宽表示矩形的方法 w, h分别表示宽度和高度 double w, h; Rect() {} Rect(double _w,double _h) : w(_w),h(_h) {} }; struct Rect_2 { // 表示矩形，左下角坐标是(xl, yl)，右上角坐标是(xh, yh) double xl, yl, xh, yh; Rect_2() {} Rect_2(double _xl,double _yl,double _xh,double _yh) : xl(_xl),yl(_yl),xh(_xh),yh(_yh) {} }; struct Circle { //圆 Point c; double r; Circle() {} Circle(Point _c,double _r) :c(_c),r(_r) {} }; typedef vector<Point> Polygon; // 二维多边形 typedef vector<Point> Points; // 二维点集 /////////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////// //基本函数区 inline double max(double x,double y) { return x > y ? x : y; } inline double min(double x, double y) { return x > y ? y : x; } inline bool ZERO(double x) // x == 0 { return (fabs(x) < EPS); } inline bool ZERO(Point p) // p == 0 { return (ZERO(p.x) && ZERO(p.y)); } inline bool ZERO(Point3D p) // p == 0 { return (ZERO(p.x) && ZERO(p.y) && ZERO(p.z)); } inline bool EQ(double x, double y) // eqaul, x == y { return (fabs(x - y) < EPS); } inline bool NEQ(double x, double y) // not equal, x != y { return (fabs(x - y) >= EPS); } inline bool LT(double x, double y) // less than, x < y { return ( NEQ(x, y) && (x < y) ); } inline bool GT(double x, double y) // greater than, x > y { return ( NEQ(x, y) && (x > y) ); } inline bool LEQ(double x, double y) // less equal, x <= y { return ( EQ(x, y) || (x < y) ); } inline bool GEQ(double x, double y) // greater equal, x >= y { return ( EQ(x, y) || (x > y) ); } // 注意！！！ // 如果是一个很小的负的浮点数 // 保留有效位数输出的时候会出现-0.000这样的形式， // 前面多了一个负号 // 这就会导致错误！！！！！！ // 因此在输出浮点数之前，一定要调用次函数进行修正！ inline double FIX(double x) { return (fabs(x) < EPS) ? 0 : x; } ////////////////////////////////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////////////////////////////// //二维矢量运算重载 bool operator==(Point p1, Point p2) { return ( EQ(p1.x, p2.x) && EQ(p1.y, p2.y) ); } bool operator!=(Point p1, Point p2) { return ( NEQ(p1.x, p2.x) || NEQ(p1.y, p2.y) ); } bool operator<(Point p1, Point p2) { if (NEQ(p1.x, p2.x)) { return (p1.x < p2.x); } else { return (p1.y < p2.y); } } Point operator+(Point p1, Point p2) { return Point(p1.x + p2.x, p1.y + p2.y); } Point operator-(Point p1, Point p2) { return Point(p1.x - p2.x, p1.y - p2.y); } double operator*(Point p1, Point p2) // 计算叉乘 p1 × p2 { return (p1.x * p2.y - p2.x * p1.y); } double operator&(Point p1, Point p2) { // 计算点积 p1·p2 return (p1.x * p2.x + p1.y * p2.y); } double Norm(Point p) // 计算矢量p的模 { return sqrt(p.x * p.x + p.y * p.y); } /*-------------------基本函数区------------------*/ // 把矢量p旋转角度angle (弧度表示) // angle > 0表示逆时针旋转 // angle < 0表示顺时针旋转 Point Rotate(Point p, double angle) { Point result; result.x = p.x * cos(angle) - p.y * sin(angle); result.y = p.x * sin(angle) + p.y * cos(angle); return result; } // 判断二维平面上点是否在线段上 // 输入：任意点p，和任意直线L // 输出：p在直线上返回1，否则返回0 bool OnSeg(Point p, Line L) { return ( ZERO( (L.p1 - p) * (L.p2 - p) ) && LEQ((p.x - L.p1.x)*(p.x - L.p2.x), 0) && LEQ((p.y - L.p1.y)*(p.y - L.p2.y), 0) ); } //求两条直线之间的关系（二维） //输入：两条不为点的直线 //输出：相交返回XIANGJIAO和点p,平行返回PINGXING,共线返回GONGXIAN int LineAndLine(Line L1,Line L2,Point &p) { Point px,py; px = L1.p1 - L1.p2; py = L2.p1 - L2.p2; if( EQ(px*py,0) )//平行或者共线 { if( ZERO( (L2.p1-L1.p1)*py ) ) //共线 { return GONGXIAN; } return PINXING; } double xa,xb,xc,ya,yb,yc; xa=(L1.p2.y-L1.p1.y); xb=(L1.p1.x-L1.p2.x); xc=(L1.p1.y*L1.p2.x-L1.p1.x*L1.p2.y); ya=(L2.p2.y-L2.p1.y); yb=(L2.p1.x-L2.p2.x); yc=(L2.p1.y*L2.p2.x-L2.p1.x*L2.p2.y); p.y = (xa*yc-xc*ya)/(xb*ya-xa*yb); p.x = (xb*yc-xc*yb)/(xa*yb-xb*ya); return XIANGJIAO; } /*---------------------代码区---------------------------*/ int SegAndSeg(Line L1,Line L2,Point &p) { double signx,signy; //跨立实验 if( LEQ(signx=( ((L1.p2-L1.p1)*(L1.p1-L2.p1))*((L1.p2-L1.p1)*(L1.p1-L2.p2)) ),0) && LEQ(signy=( ((L2.p2-L2.p1)*(L2.p1-L1.p1))*((L2.p2-L2.p1)*(L2.p1-L1.p2)) ),0) ) { if( ZERO(signx) && ZERO(signy) ) { //线段共线 signx = min( max(L1.p1.x,L1.p2.x),max(L2.p1.x,L2.p2.x) )- max( min(L1.p1.x,L1.p2.x),min(L2.p1.x,L2.p2.x) ); signy = min( max(L1.p1.y,L1.p2.y),max(L2.p1.y,L2.p2.y) )- max( min(L1.p1.y,L1.p2.y),min(L2.p1.y,L2.p2.y) ); if( ZERO(signx) && ZERO(signy) ) //说明共线，且相交一点 { if(L1.p1==L2.p1||L1.p1==L2.p2) p=L1.p1; if(L1.p2==L2.p1||L1.p2==L2.p2) p=L1.p2; return XIANGJIAO; } else if( GEQ(signx, 0) && GEQ(signy, 0) ) { return CHONGDIE; } else { return XIANGLI; } } return LineAndLine(L1, L2, p); } return XIANGLI; } int main(int argc, const char * argv[]) { /* Line a,b; while(cin>>a.p1.x>>a.p1.y>>a.p2.x>>a.p2.y) { cin>>b.p1.x>>b.p1.y>>b.p2.x>>b.p2.y; Point p; int sign=SegAndSeg(a, b, p); if(sign==XIANGJIAO) { printf("相交:(%lf,%lf) ",p.x,p.y); } else if(sign==CHONGDIE) printf("重叠 "); else if(sign==XIANGLI) printf("相离 "); } */ int n; Line ls[33],ls1[33]; Point ps[2][55]; while(scanf("%d",&n) && n) { ps[0][0].x=0; ps[0][0].y=0; for(int i=0;i<n;i++) { scanf("%lf",&ls[i].p1.x); ls[i].p1.y=0; ps[0][i+1].x = ls[i].p1.x; ps[0][i+1].y = 0; } ps[0][n+1].x=1; ps[0][n+1].y=0; for(int i=0;i<n;i++) { scanf("%lf",&ls[i].p2.x); ls[i].p2.y=1; } for(int i=0;i<n;i++) { scanf("%lf",&ls1[i].p1.y); ls1[i].p1.x=0; } for(int i=0;i<n;i++) { scanf("%lf",&ls1[i].p2.y); ls1[i].p2.x=1; } ls1[n].p1.x=0; ls1[n].p1.y=1; ls1[n].p2.x=1; ls1[n].p2.y=1; int a=0,b=1; double mi = -1; for(int i=0;i<=n;i++) { ps[b][0] = ls1[i].p1; for(int j=0;j<n;j++) { SegAndSeg(ls1[i], ls[j], ps[b][j+1]); } ps[b][n+1] = ls1[i].p2; for(int j=0;j<=n;j++) { double tmp = fabs( (ps[b][j]-ps[b][j+1])*(ps[a][j+1]-ps[b][j+1]) )/2+ fabs( (ps[b][j]-ps[a][j])*(ps[a][j+1]-ps[a][j]) )/2; mi=max(tmp,mi); } swap(a,b); } printf("%.6lf ",mi); } return 0; }