swust oj 249 凸包面积

输入

多组测试数据。第一行是一个整数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

一个凸包写了两天也是醉醉的~，最开始用快包写，发现求不了面积好像…所以后来就用了graham算法，大意就是先找到一个基准点，就是横坐标最小的情况下，纵坐标最小的点，然后开始对其他的点和基准点角度大小进行排序，然后开始遍历，要保证每个新的点要在上一个点的上面，即使得边向外凸即可。注意要删掉排序时角度相同的点，以便于计算面积。
#include<iostream>
#include<algorithm>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstdio>
#include<cstring>

using namespace std;
struct point
{
	int x, y;
};
point p[10000];
int ans[10000];
int n;
int k = 0;
int chas(point a, point b, point c)
{
	return (c.x - a.x)*(b.y - a.y) - (b.x - a.x)*(c.y - a.y);
}
bool cmp(point a, point b)
{
	int s = chas(p[0], a, b);
	if (s > 0 || (s == 0 && pow(a.x, 2) + pow(a.y, 2) > pow(b.x, 2) + pow(b.y, 2)))
	{
		return true;
	}
	else
		return false;
}
void swap(point &a, point &b)
{
	point t = a;
	a = b;
	b = t;
}

void graham(int m)
{
	k = 0;
	ans[k++] = 0;
	ans[k++] = 1;
	ans[k++] = 2;
	for (int i = 3; i < m; i++)
	{
		
		for (int t1 = ans[k - 2], t2 = ans[k - 1]; chas(p[t1],p[t2], p[i] ) <= 0; t1 = ans[k - 2], t2 = ans[k - 1])
		{
			k--;
		}
		ans[k++] = i;
	}
}

int main()
{
	int t;
	scanf("%d", &t);
	while (t--)
	{
		
		scanf("%d", &n);
		
		int minl = 0x3fff, minid;
		for (int i = 0; i < n; i++)
		{
			scanf("%d %d", &p[i].x, &p[i].y);
			if (p[i].x < minl)
			{
				minl = p[i].x;
				minid = i;
			}
			else if (minl == p[i].x && p[i].y < p[minid].y)
			{

				minl = p[i].x;
				minid = i;
			}
		}
		if (n<= 2) {
			printf("0.0\n");
			continue;
		}
		swap(p[0], p[minid]);
		sort(p + 1, p + n,cmp);
		int m = 2;
		for (int i = 2; i < n; i++)
		{
			if (chas(p[0], p[i - 1], p[i]) != 0)
			{
				p[m++] = p[i];
			}
		}

		graham(m);
		double mian = 0;

		while (k >= 2)
		{
			int t1 = ans[k - 2], t2 = ans[k - 1];
			double m = chas(p[0], p[t1], p[t2]) / 2.0;
			if (m < 0)
			{
				m = abs(m);
			}
			mian += m;
			k--;
		}
		printf("%.1lf\n", mian);
	}
	return 0;
}