题目地址：http://poj.org/problem?id=1113
先做个凸包求出最小的长度
因为要远离至少L，所以把凸包的每个线段平移远离L，同时在每个顶点做半径为L的扇形
每个顶点的扇形弧长加起来正好是一个半径为L的圆的周长
所以答案就是凸包求出来的周长加上半径为L的圆的周长，别忘了答案要四舍五入
1）极角序法
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
#define Vector Point
const double EPS=1e-6;
const double PI=acos(-1);
//极角序 Graham扫描法
struct Point{double x,y;Point(double x,double y) :x(x),y(y){}Vector operator - (const Point& p){return Vector(x-p.x,y-p.y);}bool operator < (const Point& p) const { //注意取下左点,最下的最左 if(p.y==y) return x<p.x;return y<p.y;}
};vector<Point> points;
vector<Point> stack;double cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;
}
int Sign(double x){ if(fabs(x)<EPS) return 0;return x<0?-1:1;
}
double dist(const Point& a,const Point& b){return hypot(fabs(a.x-b.x),fabs(a.y-b.y));
}
struct cmp{Point p0;cmp(Point p):p0(p){}bool operator () (Point p1,Point p2) const {int s=Sign(cross(p1-p0,p2-p0));if(s>0) return true;else if(s<0) return false;else {if(dist(p1,p0)<dist(p0,p2)) return true;else return false;}}
};int Graham()
{if(points.size()<3) return 0;stack.clear();sort(points.begin(),points.end()); //找出下左的点 sort(points.begin()+1,points.end(),cmp(points[0]));stack.push_back(points[0]); stack.push_back(points[1]); stack.push_back(points[2]);for(int i=3;i<points.size();i++){for(;;){Point p2=*(stack.end()-1);Point p1=*(stack.end()-2);if(Sign(cross(p2-p1,points[i]-p2))<=0) //小于零代表向右拐或直走 stack.pop_back();else break;}stack.push_back(points[i]); //i点肯定是向右拐的 }
}
int main()
{int n,L; int x,y;cin>>n>>L;while(n--){scanf("%d%d",&x,&y);points.push_back(Point(x,y));}Graham();double area=0;for(int i=0;i<stack.size();i++){area+=dist(stack[i],stack[(i+1)%stack.size()]);}area+=PI*2*L;printf("%d\n",(int)round(area));return 0;
}
2）水平序法
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
#define Vector Point
const double EPS=1e-6;
const double PI=acos(-1); //水平序Graham扫描法求凸包
struct Point{double x,y;Point(double x,double y) :x(x),y(y){}Vector operator - (const Point& p){return Vector(x-p.x,y-p.y);}bool operator < (const Point& p) const { //注意取下左点 if(p.y==y) return x<p.x;return y<p.y;}
};vector<Point> points;
vector<Point> stack;double cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;
}
int Sign(double x){ if(fabs(x)<EPS) return 0;return x<0?-1:1;
}
double dist(const Point& a,const Point& b){return hypot(fabs(a.x-b.x),fabs(a.y-b.y));
}
int Graham()
{if(points.size()<3) return 0;stack.clear();sort(points.begin(),points.end());stack.push_back(points[0]);stack.push_back(points[1]);int n=points.size(); for(int i=2;i<n;i++){while(stack.size()>1){ //一定要这一条，因为第二个点不一定是凸包可能会pop，而极角排序的肯定是凸包中的点 Point p2=*(stack.end()-1);Point p1=*(stack.end()-2);if(Sign(cross(p2-p1,points[i]-p2))<0) //不加等于，可以保留凸包上的点 stack.pop_back();else break;}stack.push_back(points[i]);} int size=stack.size();stack.push_back(points[n-2]); //因为此时栈顶元素是points[n-1],下一个就是n-2for(int i=n-3;i>=0;i--){while(stack.size()>size){Point p2=*(stack.end()-1);Point p1=*(stack.end()-2);if(Sign(cross(p2-p1,points[i]-p2))<0)stack.pop_back();else break;}stack.push_back(points[i]);}stack.pop_back(); //points[0]被重复push两次了
} int main()
{int n,L; int x,y;cin>>n>>L;while(n--){scanf("%d%d",&x,&y);points.push_back(Point(x,y));}Graham();double area=0;for(int i=0;i<stack.size();i++){area+=dist(stack[i],stack[(i+1)%stack.size()]);}area+=PI*2*L;printf("%d\n",(int)round(area));return 0;
}