103北市賽 領土

/*凸包與面積凸包演算法Andrew's Monotone Chain 面積計算公式Shoelace formula*/#include <vector>#include <algorithm>#include <cstdio>#include <cmath>using namespace std; struct point{ int x,y; point(){ x=0,y=0; } point(int _x,int _y){ x=_x,y=_y; } bool operator <(const point &b) const { if (x==b.x) return y<b.y; else return x<b.x; } int operator %(const point &b) const { //外積 return x*b.y-y*b.x; } point operator -(const point &b) const { //兩點相減 point a(x-b.x,y-b.y); return a; } }; int cross(point a,point b){ return a%b; } int area(vector<point> p){//Shoelace formula int ans=0; for(int i=0;i<p.size();i++){ ans+=cross(p[i],p[(i+1)%p.size()]); } return ans; } vector<point> map; int main(){ int n,x,y; point a; scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d %d",&x,&y); a.x=x; a.y=y; map.push_back(a); } sort(map.begin(),map.end());//Andrew's Monotone Chain開始 //for(int i=0;i<map.size();i++) cout << map[i].x << " " << map[i].y<< endl; vector<point> ans(map.size()*2); int top=0; for(int i=0;i<map.size();i++){//下側凸包 while((top>1)&&(cross(map[i]-ans[top-1],ans[top-1]-ans[top-2])<=0)) top--; ans[top++]=map[i]; } int t=top; for(int i=map.size()-2;i>=0;i--){//上側凸包 while((top>t)&&(cross(map[i]-ans[top-1],ans[top-1]-ans[top-2])<=0)) top--; ans[top++]=map[i]; } ans.resize(top-1);//Andrew's Monotone Chain結束 int ar=area(ans); printf("%d\n", (abs(ar)+1)/2); }