LINK

题意：给出点集，求凸包的面积

思路：主要是求面积的考察，固定一个点顺序枚举两个点叉积求三角形面积和除2即可

/** @Date    : 2017-07-19 16:07:11  * @FileName: POJ 3348 凸包面积 叉积.cpp  * @Platform: Windows  * @Author  : Lweleth (SoungEarlf@gmail.com)  * @Link    : https://github.com/  * @Version : $Id$  */#include <stdio.h>#include <iostream>#include <string.h>#include <algorithm>#include <utility>#include <vector>#include <map>#include <set>#include <string>#include <stack>#include <queue>#include <math.h>//#include <bits/stdc++.h>#define LL long long#define PII pair<int ,int>#define MP(x, y) make_pair((x),(y))#define fi first#define se second#define PB(x) push_back((x))#define MMG(x) memset((x), -1,sizeof(x))#define MMF(x) memset((x),0,sizeof(x))#define MMI(x) memset((x), INF, sizeof(x))using namespace std;const int INF = 0x3f3f3f3f;const int N = 1e5+20;const double eps = 1e-8;struct point{	double x, y;	point(){}	point(double _x, double _y){x = _x, y = _y;}	point operator -(const point &b) const	{		return point(x - b.x, y - b.y);	}	double operator *(const point &b) const 	{		return x * b.x + y * b.y;	}	double operator ^(const point &b) const	{		return x * b.y - y * b.x;	}};double xmult(point p1, point p2, point p0)  {      return (p1 - p0) ^ (p2 - p0);  }  double distc(point a, point b){	return sqrt((double)((b - a) * (b - a)));}int sign(double x){	if(fabs(x) < eps)		return 0;	if(x < 0)		return -1;	else 		return 1;}int cmpC(point a, point b)//水平序排序{	return sign(a.x - b.x) < 0 || (sign(a.x - b.x) == 0 && sign(a.y - b.y) < 0);}point stk[10100];int Graham(point *p, int n)//水平序{	sort(p, p + n, cmpC);	int top = 0;	for(int i = 0; i < n; i++)	{		while(top >= 2 && sign(xmult(stk[top - 2], stk[top - 1], p[i])) < 0)			top--;		stk[top++] = p[i];	}	int tmp = top;	for(int i = n - 2; i >= 0; i--)	{		while(top > tmp && sign(xmult(stk[top - 2],stk[top - 1] ,p[i] )) < 0)			top--;		stk[top++] = p[i];	}	if(n > 1)		top--;	return top;}double Area(point *p, int n){	double ans = 0;	for(int i = 1; i < n - 1; i++)		ans+= xmult(p[i], p[i + 1], p[0]);	return ans / 2;}point p[10100];double x, y;int n;int main(){	while(cin >> n)	{		for(int i = 0; i < n; i++)		{			scanf("%lf%lf", &x, &y);			p[i] = point(x, y);		}		int m = Graham(p, n);		/*for(int i = 0; i < m; i++)			printf("%lf %lf\n", stk[i].x, stk[i].y);*/		double ans = Area(stk, m);		printf("%d\n", (int)(ans / 50));	}    return 0;}

POJ 3348 Cows 凸包 求面积