103北市賽 3.領土 (Territory)

想法：

滿裸的凸包+有向面積題。
小高一沒教計算幾何哭哭喔QAQ。

Code：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#define maxn 10004
using namespace std;
struct point
{
    typedef int T;
    T x,y;
    point():
        x(0),y(0){}
    point(T _x,T _y):
        x(_x),y(_y){}
    bool operator <(const point &b) const
    {return x==b.x ? y<b.y : x<b.x;}
    bool operator ==(const point &b) const
    {return x==b.x && y==b.y;}
    point operator +(const point &b) const
    {return point(x+b.x,y+b.y);}
    point operator -(const point &b) const
    {return point(x-b.x,y-b.y);}
    T operator *(const point &b) const //dot
    {return x*b.x+y*b.y;}
    T operator %(const point &b) const //cross
    {return x*b.y-y*b.x;}
    point operator *(const T &b) const
    {return point(x*b,y*b);}
    double abs()
    {return sqrt(abs2());}
    T abs2()
    {return x*x+y*y;}
};
int cross(point o,point a,point b)
{return (a-o) % (b-o);}
int dot(point o,point a,point b)
{return (a-o) * (b-o);}
vector<point> convex_hull(vector<point> &pt)
{
    sort(pt.begin(),pt.end());
    int top=0;
    vector<point> stk(pt.size()*2);
    for(int i=0;i<pt.size();i++)
    {
        while(top>=2 && cross(stk[top-2],stk[top-1],pt[i])<=0)
            top--;
        stk[top++]=pt[i];
    }
    for(int i=pt.size()-2,t=top+1;i>=0;i--)
    {
        while(top>=t && cross(stk[top-2],stk[top-1],pt[i])<=0)
            top--;
        stk[top++]=pt[i];
    }
    stk.resize(top-1);
    return stk;
}
vector<point> ar;
#define pb push_back
int area(vector<point> pt)
{
    int ret=0;
    for(int i=0;i<pt.size();i++)
        ret+=pt[i]%pt[(i+1)%pt.size()];
    return abs(ret);
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0,x,y;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        ar.pb(point(x,y));
    }
    int ans=area(convex_hull(ar));
    printf("%d\n",(ans+1)/2);
    return 0; 
}