题意：给出点集，求凸包的面积
思路：主要是求面积的考察，固定一个点顺序枚举两个点叉积求三角形面积和除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;
}