题目大意：给定曼哈顿空间下的一个多边形，，求这个多边形的凸包的周长和面积
注意是曼哈顿空间
第一问直接用个最小的矩形框一下就好
第二问就要求曼哈顿空间内的凸包了
容易YY出来曼哈顿空间下的凸包一定是这种东西
我们将这个凸包分成左上 右上 左下 右下四部分
那么每部分都是一个单调增的点序列 扫一遍就行
求出凸包上的关键点之后(图中所有凸出来的点)计算下面积即可
此外应某人不想这么快看到题解的要求就让它审核一下吧 放个链接啥的
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define M 100100#define INF 0x3f3f3f3fusing namespace std;struct Point{long long x,y;friend istream& operator >> (istream &_,Point &p){int x,y;scanf("%d%d",&x,&y);p.x=x;p.y=y;return _;}bool operator < (const Point &p) const{if(x!=p.x)return x<p.x;return y<p.y;}}points[M];int n;long long min_y=INF,max_y=-INF,area;void Get_Convex_Hull(){static Point *stack[M];int i,top=0;for(i=1;i<=n;i++){if(!top||points[i].y>=stack[top]->y)stack[++top]=&points[i];if(points[i].y==max_y)break;}for(i++;i<=n;i++){while(points[i].y>stack[top]->y)stack[top–]=0x0;stack[++top]=&points[i];}for(i=2;i<=top;i++)area+=min(stack[i-1]->y,stack[i]->y)*(stack[i]->x-stack[i-1]->x);top=0;for(i=1;i<=n;i++){if(!top||points[i].y<=stack[top]->y)stack[++top]=&points[i];if(points[i].y==min_y)break;}for(i++;i<=n;i++){while(points[i].y<stack[top]->y)stack[top–]=0x0;stack[++top]=&points[i];}for(i=2;i<=top;i++)area-=max(stack[i-1]->y,stack[i]->y)*(stack[i]->x-stack[i-1]->x);}int main(){int i;cin>>n;for(i=1;i<=n;i++){cin>>points[i];min_y=min(min_y,points[i].y);max_y=max(max_y,points[i].y);}sort(points+1,points+n+1);cout<<( (max_y-min_y)+(points[n].x-points[1].x)<<1 )<<endl;Get_Convex_Hull();cout<<area<<endl;return 0;}
每一个成功者都有一个开始。勇于开始，才能找到成功的路。
