凸包面积
目录
麦兜是个淘气的孩子。一天，他在玩钢笔的时候把墨水洒在了白色的墙上。再过一会，麦兜妈就要回来了，麦兜为了不让妈妈知道这件事情，就想用一个白色的凸多边形把墙上的墨点盖住。你能告诉麦兜最小需要面积多大的凸多边形才能把这些墨点盖住吗？现在，给出了这些墨点的坐标，请帮助麦兜计算出覆盖这些墨点的最小凸多边形的面积。
输入
多组测试数据。第一行是一个整数T，表明一共有T组测试数据。 每组测试数据的第一行是一个正整数N(0< N < = 105)，表明了墨点的数量。接下来的N行每行包含了两个整数Xi和Yi（0<=Xi,Yi<=2000），表示每个墨点的坐标。每行的坐标间可能包含多个空格。
输出
每行输出一组测试数据的结果，只需输出最小凸多边形的面积。面积是个实数，小数点后面保留一位即可，不需要多余的空格。
样例输入
2 4 0 0 1 0 0 1 1 1 2 0 0 0 1
样例输出
1.0
0.0
解题大致思路
如下图所示的凸包为例
要计算该凸包的面积，我们可以将凸包换分为多个三角形来进行计算入下图所示
划分成这样的三角形，首先需要将数据集里面的a,b两点确认出来，来作为初始划分时候的三角形底边，同时以ab边为界，将该凸包分成了上下两个凸包。然后再在上下两个凸包中分别找离ab边距离最远的点，即上包最远点为c点，下包最远点为f点，则分别构成三角形abc，三角形afb,在这两个三角形内部的点就不需要在进行考虑了。
在三角形外部的点则根据该点在三角形那一条边外面，则就以那一条边为底，然后在该边外侧寻找距离最远点(如:点d在cb边外侧且为最远点则构成三角形cdb)
判断a,b两点的方法:
遍历数据集将数据集,将数据集中x坐标值最小，且y坐标值最小的点筛选出来即点a.
将数据集中的x坐标值最大且y坐标值最大的点筛选出来即点b
以ab边作为分界线分离上下包的方法
将向量ab表示出来即ab=(x1,x2),设其他点为Oi(i=1,2,3...),则向量aOi=(s,n),通过向量的叉乘的正负值来判断上下包，正值为上包
即x1*n-x2*s的正负。
将上下包分离出来过后及遍历上下包将最远距离点也为三角形面积最大点计算出来
使用下面的行列式进行计算
该行列式的计算结果的绝对值的一半及为三角形面积
代码实现
#include<stdio.h>
#include <string.h>
#include <stdlib.h>
struct position
{
int x, y;
};
position sum[105];
int num = 0;
float area = 0;
int topb(position pos[], position a, position b, int n)
{
position p1[100], p2[100];
if (n <= 0)
{
//if(n==1)
//sum[num++]=pos[0];
return 0;
}
int i, s, j, k = 0, l = 0;
float max = 0;
for (i = 0; i<n; i++)
{
s = a.x*b.y + pos[i].x*a.y + b.x*pos[i].y - pos[i].x*b.y - b.x*a.y - a.x*pos[i].y;//上包最远点;
if (s>max)
{
max = s;
j = i;
}
}
area += (max / 2);
sum[num++] = pos[j];
int x1, y1, x2, y2, x3, y3, x4, y4;
x1 = pos[j].x - a.x;
y1 = pos[j].y - a.y;
x3 = b.x - pos[j].x;
y3 = b.y - pos[j].y;
for (i = 0; i<n; i++)
{
x2 = pos[i].x - a.x;
y2 = pos[i].y - a.y;
x4 = pos[i].x - pos[j].x;
y4 = pos[i].y - pos[j].y;
if ((x1*y2 - x2*y1)>0)
{
p1[k++] = pos[i];
}
if ((x3*y4 - x4*y3)>0)
{
p2[l++] = pos[i];
}
}
topb(p1, a, pos[j], k);
topb(p2, pos[j], b, l);
}
int dowb(position pos[], position a, position b, int n)
{
position p1[100], p2[100];
if (n <= 0)
{
//if(n==1)
//sum[num++]=pos[0];
return 0;
}
int i, s, j, k = 0, l = 0;
float max = 0;
for (i = 0; i<n; i++)
{
s = a.x*b.y + pos[i].x*a.y + b.x*pos[i].y - pos[i].x*b.y - b.x*a.y - a.x*pos[i].y;//下包最远点，既构成的三角形面积最大点，下包该值为负;
if (s<max)
{
max = s;
j = i;
}
}
area -= (max / 2);
sum[num++] = pos[j];
int x1, y1, x2, y2, x3, y3, x4, y4;
x1 = pos[j].x - a.x;
y1 = pos[j].y - a.y;
x3 = b.x - pos[j].x;
y3 = b.y - pos[j].y;
for (i = 0; i<n; i++)
{
x2 = pos[i].x - a.x;
y2 = pos[i].y - a.y;
x4 = pos[i].x - pos[j].x;
y4 = pos[i].y - pos[j].y;
if ((x1*y2 - x2*y1)<0)
{
p1[k++] = pos[i];
}
if ((x3*y4 - x4*y3)<0)
{
p2[l++] = pos[i];
}
}
dowb(p1, a, pos[j], k);
dowb(p2, pos[j], b, l);
}
int main()
{
position pos[105], ab, top[103], dow[103], Oi;
int t, n, k, m, j, q;
scanf("%d", &t);
while (t--)
{
num = area = 0;
k = m = 0;
j = q = 0;
scanf("%d", &n);
int i;
for (i = 0; i<n; i++)
{
scanf("%d%d", &pos[i].x, &pos[i].y);
if (pos[i].x<pos[k].x || (pos[i].x == pos[k].x&&pos[i].y<pos[k].y))
{
k = i;
}
if (pos[i].x>pos[m].x || (pos[i].x == pos[m].x&&pos[i].y>pos[m].y))
{
m = i;
}
}
if (n <= 2)
printf("0.0\n");
else
{
ab.x = pos[m].x - pos[k].x;//向量
ab.y = pos[m].y - pos[k].y;
for (i = 0; i<n; i++)
{
Oi.x = pos[i].x - pos[k].x;//向量
Oi.y = pos[i].y - pos[k].y;
if ((Oi.y*ab.x - Oi.x*ab.y)<0)//将上下包分出来
{
dow[j] = pos[i];
j++;
}
if ((Oi.y*ab.x - Oi.x*ab.y)>0)
{
top[q] = pos[i];
q++;
}
}
sum[num++] = pos[k];
sum[num++] = pos[m];
topb(top, pos[k], pos[m], q);//上包
dowb(dow, pos[k], pos[m], j);//下包
printf("%.1f\n", area);
}
}
return 0;
}
