(hdu 7.1.7)Wall(求凸包的周長——求將所有點圍起來的最小凸多邊形的周長)
題目：
Wall
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 119 Accepted Submission(s): 47
Problem DescriptionOnce upon a time there was a greedy King who ordered his chief Architect to build a wall around the King's castle. The King was so greedy, that he would not listen to his Architect's proposals to build a beautiful brick wall with a perfect shape and nice tall towers. Instead, he ordered to build the wall around the whole castle using the least amount of stone and labor, but demanded that the wall should not come closer to the castle than a certain distance. If the King finds that the Architect has used more resources to build the wall than it was absolutely necessary to satisfy those requirements, then the Architect will loose his head. Moreover, he demanded Architect to introduce at once a plan of the wall listing the exact amount of resources that are needed to build the wall.
Your task is to help poor Architect to save his head, by writing a program that will find the minimum possible length of the wall that he could build around the castle to satisfy King's requirements.
The task is somewhat simplified by the fact, that the King's castle has a polygonal shape and is situated on a flat ground. The Architect has already established a Cartesian coordinate system and has precisely measured the coordinates of all castle's vertices in feet.
InputThe first line of the input file contains two integer numbers N and L separated by a space. N (3 <= N <= 1000) is the number of vertices in the King's castle, and L (1 <= L <= 1000) is the minimal number of feet that King allows for the wall to come close to the castle.
Next N lines describe coordinates of castle's vertices in a clockwise order. Each line contains two integer numbers Xi and Yi separated by a space (-10000 <= Xi, Yi <= 10000) that represent the coordinates of ith vertex. All vertices are different and the sides of the castle do not intersect anywhere except for vertices.
OutputWrite to the output file the single number that represents the minimal possible length of the wall in feet that could be built around the castle to satisfy King's requirements. You must present the integer number of feet to the King, because the floating numbers are not invented yet. However, you must round the result in such a way, that it is accurate to 8 inches (1 foot is equal to 12 inches), since the King will not tolerate larger error in the estimates.
This problem contains multiple test cases!
The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.
The output format consists of N output blocks. There is a blank line between output blocks.
Sample Input
1
9 100
200 400
300 400
300 300
400 300
400 400
500 400
500 200
350 200
200 200
Sample Output
1628
SourceNortheastern Europe 2001
RecommendJGShining
題目分析：
求凸包的周長。再求圖報的周長前，首先要做的是計算凸包——找到將所有點圍起來的最小凸多邊形。
對於找到凸包的算法，以下代碼用的是graham算法，對這個算法不太熟悉的童鞋可以先看一下：
www.Bkjia.com
代碼如下：
/*
* g.cpp
*
* Created on: 2015年3月16日
* Author: Administrator
*/
#include
#include
#include
#include
using namespace std;
const double epsi = 1e-8;
const double pi = acos(-1.0);
const int maxn = 1001;
struct PPoint{//結構體盡量不要定義成Point這種,容易和C/C++本身中的變量同名
double x;
double y;
PPoint(double _x = 0,double _y = 0):x(_x),y(_y){
}
PPoint operator - (const PPoint& op2) const{
return PPoint(x - op2.x,y - op2.y);
}
double operator^(const PPoint &op2)const{
return x*op2.y - y*op2.x;
}
};
inline int sign(const double &x){
if(x > epsi){
return 1;
}
if(x < -epsi){
return -1;
}
return 0;
}
inline double sqr(const double &x){
return x*x;
}
inline double mul(const PPoint& p0,const PPoint& p1,const PPoint& p2){
return (p1 - p0)^(p2 - p0);
}
inline double dis2(const PPoint &p0,const PPoint &p1){
return sqr(p0.x - p1.x) + sqr(p0.y - p1.y);
}
inline double dis(const PPoint& p0,const PPoint& p1){
return sqrt(dis2(p0,p1));
}
int n;
double l;
PPoint p[maxn];
PPoint convex_hull_p0;
inline bool convex_hull_cmp(const PPoint& a,const PPoint& b){
return sign(mul(convex_hull_p0,a,b)>0)|| sign(mul(convex_hull_p0,a,b)) == 0 && dis2(convex_hull_p0,a) < dis2(convex_hull_p0,b);
}
/**
* 計算點集a[]的凸包b[]。其中點集a有n個元素
*/
int convex_hull(PPoint* a,int n,PPoint* b){
if(n < 3){//如果頂點數小於3,構不成一個凸包
//輸出失敗信息
printf("wrong answer ,cause of n smaller than 3\n");
return -1;
}
int i;
for(i = 1 ; i < n ; ++i){//遍歷點集中的每一個點
//尋找最低點(所謂的最低點就是最靠左下角的點)
if(sign(a[i].x - a[0].x) < 0 || (sign(a[i].x - a[0].x) == 0 && sign(a[i].y < a[0].y) < 0 )){
swap(a[i],a[0]);
}
}
convex_hull_p0 = a[0];
sort(a,a+n,convex_hull_cmp);//排序
int newn = 2;
b[0] = a[0];
b[1] = a[1];
/**
* 在剩下的點中不斷前進,如果當前點在前進方向左側,
* 則將當前點進棧,否則將最近入棧的點出棧.知道當前點在前進方向的左側
*/
for(i = 2 ; i < n ; ++i){
while(newn > 1 && sign(mul(b[newn-1],b[newn-2],a[i])) >= 0){
newn--;
}
b[newn++] = a[i];//江當前點進棧
}
return newn;//返回棧頂指針
}
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%d %lf",&n,&l);
int i;
for(i = 0 ; i < n ; ++i){
scanf("%lf %lf",&p[i].x,&p[i].y);
}
n = convex_hull(p,n,p);
p[n] = p[0];
double ans = 0;
for(i = 0 ; i < n ; ++i){//求凸包的周長
ans += dis(p[i],p[i+1]);
}
ans += 2*pi*l;//加上外面圍牆的周長
/**
* "."後面的是小數精度控制，這裡因為是浮點型，則取零代表不顯示小數點（取整）
* .不為零時代表最大小數位數
*/
printf("%.0lf\n",ans);
if(t != 0){//每個輸出後面都要跟一個換行
printf("\n");
}
}
return 0;
}
