POJ 1113 解题报告

时间：2010-05-28 来源：MC_ACM

一、问题Description

Once 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.

Input

The 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.

Output

Write 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.

Sample Input

9 100

200 400

300 400

300 300

400 300

400 400

500 400

500 200

350 200

200 200

Sample Output

1628

二、相关概念和算法：

一组平面上的点，求一个包含所有点的最小的凸多边形，这就是凸包问题了。这可以形象地想成这样：在地上放置一些不可移动的木桩，用一根绳子把他们尽量紧地圈起来，这就是凸包了。

常见求法

　　2.1　凸包最常用的凸包算法是Graham扫描法和Jarvis步进法。　　对于一个有三个或以上点的点集Q，过程如下：　　计算点集最右边的点为凸包的顶点的起点，如上图的P3点。　　Do　　For i = 0 To 总顶点数　　计算有向向量P3->Pi　　If 其余顶点全部在有向向量P3->Pi的左侧或右侧，则Pi点为凸包的下一顶点　　Pi点加入凸包列表　　GoTo 1　　End If　　Next　　Exit Do　　1:　　Loop　　此过程执行后，点按极角自动顺时针或逆时针排序，只需要按任意两点的次序就可以了。而左侧或右侧的判断可以用前述的矢量点积性质实现。

特殊算法

2.2　求凸包有很多方法，不过最适合OI的估计还是Graham's Scan这个方法了。它的大致方法是这样的：首先，找到所有点中最左边的（y坐标最小的），如果y坐标相同，找x坐标最小的；以这个点为基准求所有点的极角（atan2(y-y0,x-x0)），并按照极角对这些点排序，前述基准点在最前面，设这些点为P[0]..P[n-1]；建立一个栈，初始时P[0]、P[1]、P[2]进栈，对于P[3..n-1]的每个点，若栈顶的两个点与它不构成“向左转”的关系，则将栈顶的点出栈，直至没有点需要出栈以后将当前点进栈；所有点处理完之后栈中保存的点就是凸包了。　　如何判断A、B、C构成的关系不是向左转呢？如果b-a与c-a的叉乘小于0就不是。a与b的叉乘就是a.x*b.y-a.y*b.x。　　上面的这个Graham的实现比我原来按照USACO里的课文写得简单多了，主要是它通过简单的预处理保证了P[0]、P[1]以及P[n-1]肯定是凸包里的点，这样就可以避免在凸包“绕回来”的时候繁杂的处理。

三、解题说明与代码

Ø 大意：求将一个多边形包围起来，且到多边形的距离不得小于rd的包裹的最小周长。

Ø 算法: 凸包。ans=凸包周长+rd为半径的圆周长（外角和=周角）。

#include <iostream>
#include <cmath>
#include <algorithm>
#define Max 1000
#define eps 1e-8 // 定义#define eps 1e-8就是用eps表示1e-8，即0.00000001

#define PI 3.141592654
using namespace std;
struct point //顶点

{
    double x;
    double y;
    double cross;
};
point stack[Max];//储存凸包边缘顶点

point points[Max];
int NumOfVertex;//顶点数

int size;//stack长度

double r;
double sum;//边缘长度

bool cmpyx(point a,point b)//按照yx坐标排序

{
    if(a.y==b.y)
        return a.x<b.x;
    return a.y<b.y;
}
bool cmpcross(point a,point b)//按照角度大小排序

{
    if(a.cross == b.cross)
        return a.x<b.x;
    return a.cross<b.cross;
}
bool judge(point first,point second,point third)//判断是否往右拐

{
    double x1,x2,y1,y2,result;
    x1 = second.x-first.x;
    x2 = third.x-first.x;
    y1 = second.y-first.y;
    y2 = third.y-first.y;
    result = x1*y2-y1*x2;
    if(fabs(result)<eps) //判断绝对值是否小于eps

        result = 0;
    if(result<=0)//往右拐

        return true;
    return false;
}
void Cross()//计算极角（极坐标中的一个参数;极坐标一共两个参数;一个是极角一个是极径;一个函数图像上某一点到原点的距离就是极径，极径与x轴的夹角就是极角）

{
    int i;
    double x,y;
    for(i=1;i<NumOfVertex;i++)
    {
        x = (points[i].x-points[0].x);
        y = (points[i].y-points[0].y);
        points[i].cross = acos((x/(sqrt(x*x+y*y)))); //acos反余弦sqrt平方根

    }
}
void Graham()//找出凸包顶点

{
    int top=0,i;
    sort(points,points+NumOfVertex,cmpyx);
    Cross();
    sort(points+1,points+NumOfVertex,cmpcross);
    stack[0] = points[0];
    size = 1;
    for (i=1;i<NumOfVertex;i++)
    {
        while (size>1&&judge(stack[top-1],stack[top],points[i]))
        {
            size--;
            top--;
        }
        stack[++top] = points[i];
        size++;
    }
}
double caculate(point top, point top2)//计算凸包长度

{
    double x = (top.x - top2.x) * (top.x - top2.x);
    double y = (top.y - top2.y) * (top.y - top2.y);
    return sqrt(x + y);
}
int main()
{
    int i;
    while (scanf("%d%lf",&NumOfVertex,&r)!=EOF)
    {
        for(i=0;i<NumOfVertex;i++)
            scanf("%lf%lf",&points[i].x,&points[i].y);
        Graham();
        sum = 0;
        for (i=0;i<size-1;i++) // int size;//stack长度

            sum+=caculate(stack[i],stack[i+1]);
        sum+=caculate(stack[0],stack[size-1]);
        sum+=2*PI*r;
        printf("%.0lf\n",sum);
    }
    return 0;
}