poj3384

题意：求凸包面积/50，并取整。

分析：用模板。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

#define maxn 10005

struct Point
{
    double x, y;
} point[maxn], cvx[maxn];

int n, m;

bool mult(Point sp, Point ep, Point op)
{
    return (sp.x - ep.x) * (ep.y - op.y) >= (ep.x - op.x) * (sp.y - ep.y);
}

bool operator <(const Point &l, const Point &r)
{
    return l.y < r.y || (l.y == r.y && l.x < r.x);
}

int graham(Point pnt[], int n, Point res[])
{
    int i, len, top = 1;
    sort(pnt, pnt + n);
    if (n == 0)
        return 0;
    res[0] = pnt[0];
    if (n == 1)
        return 1;
    res[1] = pnt[1];
    if (n == 2)
        return 2;
    res[2] = pnt[2];
    for (i = 2; i < n; i++)
    {
        while (top && mult(pnt[i], res[top], res[top - 1]))
            top--;
        res[++top] = pnt[i];
    }
    len = top;
    res[++top] = pnt[n - 2];
    for (i = n - 3; i >= 0; i--)
    {
        while (top != len && mult(pnt[i], res[top], res[top - 1]))
            top--;
        res[++top] = pnt[i];
    }
    return top;
    // 返回凸包中点的个数
}

void input()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%lf %lf", &point[i].x, &point[i].y);
}

double areaofp(int vcount, Point plg[])
{
    int i;
    double s;
    if (vcount < 3)
        return 0;
    s = plg[0].y * (plg[vcount - 1].x - plg[1].x);
    for (i = 1; i < vcount; i++)
        s += plg[i].y * (plg[(i - 1)].x - plg[(i + 1) % vcount].x);
    return s / 2;
}

int main()
{
    //freopen("t.txt", "r", stdin);
    input();
    m = graham(point, n, cvx);
    printf("%d\n", (int)(areaofp(m, cvx) / 50));
    return 0;
}