[題解]TIOJ 1280 領土 (Territory)

TIOJ 1280 領土 (Territory)

題目連結
Submission

題目敘述
一個國家有 n 個安全哨，每一個都有座標 $(x,y)$ ，代表在座標軸上的位置。輸出該國安全哨所能圍出的最大領土。

n個點所能圍成的最大面積，其實等價於凸包的面積。與前幾題的最小凸多邊形是一模一樣的題目！

#include <bits/stdc++.h>
#define Orz ios::sync_with_stdio(0),cin.tie(0)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pii pair<int,int>
#define pdd pair<double,double>
#define int long long
#define ll long long
#define ld long double
#define N 100001
#define all(x) x.begin(),x.end()
#define eps 1e-9
#define x first
#define y second

using namespace std;

struct pt{
    int x,y;
    bool operator < (pt b){
        if(x == b.x)return y < b.y;
        return x < b.x;
    }
    bool operator > (pt b){
        if(x == b.x)return y > b.y;
        return x > b.x;
    }
    bool operator == (pt b){
        if(x-b.x == 0 && y-b.y == 0)return true;
        return false;
    }
    pt operator+(pt b) {return {x + b.x, y + b.y};} //向量相加
    pt operator-(pt b) {return {x - b.x, y - b.y};} //向量相減
    int operator^(pt b) {return x * b.y - y * b.x;} //向量外積cross
    int operator*(pt b) {return x * b.x + y * b.y;} //向量內積dot
};

vector<pt> p,temp,pp;
vector<int>  cnt;
int n,ans = 0;

bool cmp(pt a, pt b){
    if(a.x == b.x)return a.y < b.y;
    return a.x < b.x;
}

bool check(pt a,pt b,pt o){
    pt aa = a - o;
    pt bb = b - o;
    return (aa^bb) >= 0;
}

vector<pt> solve(){
    sort(all(p),cmp);
    vector<pt> h;
    for(pt i : p){
        while(h.size()>=2 && check(i,h[h.size()-1],h[h.size()-2]))
            h.pop_back();
        h.push_back(i);
    }
    int sz = h.size();
    h.pop_back();
    reverse(all(p));
    for(auto i : p){
        while(h.size()>sz && check(i,h[h.size()-1],h[h.size()-2]))
            h.pop_back();
        h.push_back(i);
    }
    return h;
}

signed main(){
    Orz;
    cin>>n;
    p.resize(n,{0,0});
    rep(i,0,n-1)cin>>p[i].x>>p[i].y;
    vector<pt> hull = solve();
    int area = 0,sz = hull.size();
    rep(i,0,sz-2){
        area += (hull[i]^hull[i+1]);
    }
    cout<<((area%2)?(area/2)+1:(area/2))<<endl;
}