题目链接:点击打开链接
== 难得的y出了一道计算几何。。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <math.h> #include <iostream> using namespace std; #define INF 999999999.9 #define PI acos(-1.0) #define ll long long struct Point { ll x, y, dis; }pt[400005], stack[400005], p0; ll top, tot; //计算几何距离 ll Dis(ll x1, ll y1, ll x2, ll y2) { return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2); } //极角比较, 返回-1: p0p1在 p0p2的右侧,返回 0:p0,p1,p2共线 int Cmp_PolarAngel(struct Point p1, struct Point p2, struct Point pb) { double delta=(p1.x-pb.x)*(p2.y-pb.y)-(p2.x-pb.x)*(p1.y-pb.y); if (delta<0.0) return 1; else if (delta==0.0) return 0; else return -1; } // 判断向量p2p3是否对 p1p2构成左旋 bool Is_LeftTurn(struct Point p3, struct Point p2, struct Point p1) { int type=Cmp_PolarAngel(p3, p1, p2); if (type<0) return true; return false; } //先按极角排,再按距离由小到大排 int Cmp(const void*p1, const void*p2) { struct Point*a1=(struct Point*)p1; struct Point*a2=(struct Point*)p2; int type=Cmp_PolarAngel(*a1, *a2, p0); if (type<0) return -1; else if (type==0) { if (a1->dis<a2->dis) return -1; else if (a1->dis==a2->dis) return 0; else return 1; } else return 1; } //求凸包 ll step[4][2] = {0,1,0,-1,1,0,-1,0}; void Solve(ll n) { ll i, k; p0.x=p0.y=INF; ll x,y; for (i=0;i<n;i++) { scanf("%I64d %I64d",&x, &y); for(ll j = 0; j < 4; j++) { Point P = {x+step[j][0], y+step[j][1]}; pt[i*4+j] = P; if (pt[i*4+j].y < p0.y) { p0.y=pt[i*4+j].y; p0.x=pt[i*4+j].x; k=i*4+j; } else if (pt[i*4+j].y==p0.y) { if (pt[i*4+j].x<p0.x) { p0.x=pt[i*4+j].x; k=i*4+j; } } } } n *= 4; pt[k]=pt[0]; pt[0]=p0; for (i=1;i<n;i++) pt[i].dis=Dis(pt[i].x,pt[i].y, p0.x,p0.y); qsort(pt+1, n-1, sizeof(struct Point), Cmp); //去掉极角相同的点 tot=1; for (i=2;i<n;i++) if (Cmp_PolarAngel(pt[i], pt[i-1], p0)) pt[tot++]=pt[i-1]; pt[tot++]=pt[n-1]; top=1; stack[0]=pt[0]; stack[1]=pt[1]; for (i=2;i<tot;i++) { while (top>=1 && Is_LeftTurn(pt[i], stack[top], stack[top-1])==false) top--; stack[++top]=pt[i]; } } inline ll Abs(ll x){return x>0?x:-x;} ll len(Point a, Point b){ return Abs(a.x-b.x) + Abs(a.y-b.y)-min(Abs(a.x-b.x), Abs(a.y-b.y)); } int main () { ll n, x, y; while (cin>>n) { Solve(n); ll ans = 0; for(ll i = 0; i < top; i++) ans += len(stack[i], stack[i+1]); ans += len(stack[top], stack[0]); cout<<ans<<endl; } return 0; }