http://poj.org/problem?id=1408
题意：给出 a1 a2 ... an
b1 b2 ... bn
c1 c2 ... cn
d1 d2 ... dn 这些点，求这些对应点连线形成的小四边形的最大面积。
思路：将所有的交点求出，同已知点一起存入二维矩阵中，枚举每个小四边形，求出其面积，找出最大的即可。
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
const double eps=1e-;//设置精度
#define max1(a1,b1) (double)a1-(double)b1>eps?(double)a1:(double)b1
struct point//点
{
double x;
double y;
} map[][];//用二维数组的结构体存储所有的点
struct line//线
{
double a,b,c;
};
line getline(point p1,point p2)//由两点求直线ax+by+c=0
{
line tmp;
tmp.a = p1.y-p2.y;
tmp.b = p2.x-p1.x;
tmp.c = p1.x*p2.y-p2.x*p1.y;
return tmp;
}
point getIntersect(line L1,line L2)//求两直线交点
{
point tmp;
tmp.x = (L1.b*L2.c-L2.b*L1.c)/(L1.a*L2.b-L2.a*L1.b);
tmp.y = (L1.c*L2.a-L2.c*L1.a)/(L1.a*L2.b-L2.a*L1.b);
return tmp;
}
double area_polygon(int n,point* p)//求多边形面积
{
double s1=,s2=;
int i;
for (i=; i<n; i++)
{
s1+=p[(i+)%n].y*p[i].x;
s2+=p[(i+)%n].y*p[(i+)%n].x;
}
return fabs(s1-s2)/;
}
int main()
{
int n;
while(~scanf("%d",&n)&&n)
{
double Max = eps;
double a,b,c,d;
map[][].x = ;//初始化已知的四个顶点的坐标
map[][].y = ;
map[][n+].x = ;
map[][n+].y = ;
map[n+][].x = ;
map[n+][].y = ;
map[n+][n+].x = ;
map[n+][n+].y = ;
for (int j = ; j <= n; j++)//输入a1 a2 ... an，并存储其坐标
{
scanf("%lf",&a);
map[][j].x = a;
map[][j].y = ;
}
for (int j = ; j <= n; j++)//输入b1 b2 ... bn，并存储其坐标
{
scanf("%lf",&b);
map[n+][j].x = b;
map[n+][j].y = ;
}
for (int i = ; i <= n; i++)//输入c1 c2 ... cn，并存储其坐标
{
scanf("%lf",&c);
map[i][].x = ;
map[i][].y = c;
}
for (int i =; i <= n; i++)//输入d1 d2 ... dn，并存储其坐标
{
scanf("%lf",&d);
map[i][n+].x = ;
map[i][n+].y = d;
}
for (int i = ; i <= n; i++)
for (int j = ; j <= n; j++)
{
line L1 = getline(map[i][],map[i][n+]);//枚举所有可相交的直线
line L2 = getline(map[][j],map[n+][j]);
point tmp = getIntersect(L1,L2);//求这两条线的交点
map[i][j].x = tmp.x;//将求得的交点坐标存入相应的数组中
map[i][j].y = tmp.y; }
point p[];//存储四边形的顶点
for (int i = ; i <= n+; i++)
{ for (int j = ; j <= n+; j++)//枚举所有四边形右上角的顶点
{
p[] = map[i][j];//以map[i][j]为右上角的顶点组成的四边形的各点
p[] = map[i][j-];
p[] = map[i-][j-];
p[] = map[i-][j];
double s = area_polygon(,p);//求四边形的面积
Max = max1(s,Max);//求最大面积
} }
printf("%.6f\n",Max);
}
return ;
}