`

poj 1113 wall (凸包问题)

阅读更多

Wall

Time Limit: 1000MS

 

Memory Limit: 10000K

Total Submissions: 17387

 

Accepted: 5627

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

Hint

结果四舍五入就可以了

 

链接如下http://poj.org/problem?id=1113

 

题目大意:就是求凸包的周长+一个圆的周长。

就是一个典型求凸包的问题,下面是代码:

 

//求凸包问题
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
using namespace std;

const double PI = 3.14159265358979;
struct point
{
    double x,y;
    double thera;
}a[1005],chs[1005];

bool cmp1(point a,point b)    //寻找左下角的点
{
    if( a.y == b.y ) return a.x < b.x;
    return a.y < b.y;
}
bool cmp2(point a,point b)
{
    if( a.thera == b.thera ) //极角相同按x位置升序
        return a.x < b.x;
    else
        return a.thera < b.thera;
}
double get_thera(point a0,point a1)     //求两点直线与x轴的夹角
{
    return atan2((a1.y-a0.y),(a1.x-a0.x));
}
double dist_2point(point a1,point a2)   //两点距离
{
    return sqrt((a1.x-a2.x)*(a1.x-a2.x)+(a1.y-a2.y)*(a1.y-a2.y));
}

bool line_3point(point a1,point a2,point a3)
{
    double P,Q,M;
    //又是那个原理:求点在直线的左边还是右边。(叉乘!)
    P=(a2.x - a1.x) * (a3.y - a1.y);
    Q=(a3.x - a1.x) * (a2.y - a1.y);
    M=P-Q;
    if(M>0)  return false;  //负数 说明在向量的右边,是顺时针旋转的。
    if(M<0)  return true;   //正数 说明在向量的左边,是逆时针旋转的。
    if(M==0) return true;  //零   说明线段的直线上,则点(x3,y3)是共线。
	return false;
}

int main()
{
    int i,n,top;
	double r,len,shan,sum;
    while(scanf("%d%lf",&n,&r)!=EOF)
    {
        len=0;
        for(i=0;i<n;i++)
            scanf("%lf%lf",&a[i].x,&a[i].y);
        ///求左下角的点(以它未基准)  y最小,若相同,x要最小。
		sort(a,a+n,cmp1);

        ///下面就是极角排序
		for(i=0;i<n;i++)    //求两点连线与x轴夹角
		    a[i].thera=get_thera(a[0],a[i]);  //得到夹角的弧度
		sort(a+1,a+n,cmp2); //对夹角进行由小到大的排序

		///下面就是Wall Graham_Scan算法
        chs[0]=a[0]; chs[1]=a[1]; chs[2]=a[2];
        top=2;
        for(i=3;i<n;i++)
        {
            while(top>=1 && line_3point(chs[top-1],chs[top],a[i]))
            {
                top--;
            }
            chs[++top]=a[i];    //chs[]就是凸包的点
        }
        ///这样求出chs[]的点就是凸包的所有顶点!!!(逆时针)

        top++;  //小心注意!因为最后chs[++top]=a[i],所以要top++!
        for(i=0;i<top;i++)
            len+=dist_2point(chs[i%top],chs[(i+1)%top]);

        shan=2.0*PI*r;
        sum=shan+len;
		printf("%.0lf\n",sum);
    }
    return 0;
}
2
1
分享到:
评论
1 楼 基德KID.1412 2011-07-27  
灰常好,嘎嘎嘎

相关推荐

    POJ1113-Wall【凸包】

    【描述】"北大POJ1113-Wall【凸包】解题报告+AC代码"表明这是一篇关于如何解决这个问题的详细报告,其中可能包含了对问题的理解、算法的选择、问题解决的步骤,以及最终通过测试的源代码(AC,Accepted的缩写,表示...

    pku_poj_2187.rar_poj 2187_凸包问题

    标题中的“pku_poj_2187.rar_poj 2187_凸包问题”表明这是一个关于北京大学(Peking University, PKU)编程竞赛平台POJ上的第2187题,题目主要涉及凸包问题。描述中的“O(nlogn)凸包问题 poj2187”提示我们解决这个...

    学习凸包(三):凸包练习 POJ 1113

    这篇博客“学习凸包(三): 凸包练习 POJ 1113”显然是关于如何通过编程解决凸包问题的一个实例。我们将深入探讨这个话题,主要关注凸包的定义、常见的求解算法以及如何用Java实现。 凸包可以被定义为一个给定集合中...

    学习凸包(五):卷包裹算法--兼解POJ1113(JAVA)

    总之,卷包裹算法是解决凸包问题的有效手段,尤其适用于二维平面上的点集。通过学习和理解这一算法,我们可以更好地应对类似POJ1113这样的编程挑战,提升我们的算法设计和编程能力。对于Java开发者来说,了解并能够...

    凸包melkman算法 cpp STL deque

    poj1113 melkman算法求凸包, 使用STL

    凸包练习: POJ 2187(JAVA)

    总结起来,"凸包练习: POJ 2187(JAVA)"是一个关于几何算法的实际应用问题,通过解决这个问题,你可以学习到如何用JAVA编程语言处理几何问题,掌握凸包算法,以及如何有效地读取、处理和输出数据。同时,这也是提升...

    POJ算法题目分类

    POJ 算法题目分类 POJ 算法题目分类是指分类所有 POJ 题目的算法思想和解决方案,本文将对算法分类进行详细的介绍。 一、基本算法 ...* 凸包:凸包是指解决问题的凸包算法,如 poj2187、poj1113。

    凸包melkman算法cpp

    凸包melkman算法cpp实现,通过poj1113题测试

    poj题目分类

    poj题目分类 POJ(Princeton Online Judge)是一個在线编程平台...4. 凸包:例如 poj2187、poj1113。 这些知识点涵盖了算法、数据结构、数学、计算几何学等领域的多个方面,为编程爱好者和学生提供了广泛的知识基础。

    poj各种分类

    寻找凸多边形的边界,用于图形分析和碰撞检测,如poj2187和poj1113。 ### 中级阶段的扩展 在初级阶段的基础上,中级阶段涵盖了更多复杂的数据结构和算法,如差分约束系统、最小费用最大流、双连通分量、强连通分支...

    POJ1321棋盘问题

    "POJ1321棋盘问题" POJ1321棋盘问题是一种经典的回溯法问题,目的是在一个给定的棋盘形状上摆放k个棋子,使得任意两个棋子不能放在同一行或者同一列。该问题可以通过回溯法来解决。 问题描述: 在一个给定的棋盘...

    POJ 放炮问题 1185

    《POJ放炮问题1185》是一个典型的动态规划问题,主要涉及到计算机科学中的算法设计与分析。问题的核心在于计算在给定的地形条件下,能够放置的最大炮数。题目来源于北京大学的在线编程平台POJ。 该问题的解决策略...

    经典 的POJ 分类

    #### 凸包问题 - **题目示例**: - POJ 2976:凸包构建与性质分析。 - POJ 3150、POJ 3422:复杂几何形状的计算。 以上是对经典POJ分类的详细解析,通过这些知识点的学习,可以帮助我们更好地理解和掌握算法与...

    POJ1004-Financial Management

    在解决此类问题时,通常会使用C++等编程语言,因此`POJ1004-Financial Management.cpp`文件很可能包含了用C++编写的源代码。代码可能包含了读取输入、处理数据、计算结果和输出答案等核心功能。同时,`POJ1004-...

    POJ.rar_poj java_poj1048

    【标题】"POJ.rar_poj java_poj1048" 涉及的知识点主要围绕编程竞赛中的“约瑟夫环”问题,这里是一个加强版,使用Java语言进行解决。 【描述】"POJ1048,加强版的约瑟夫问题 难度中等" 提示我们,这个问题是编程...

    POJ_3131.zip_POJ 八数码_poj

    标题中的“POJ_3131.zip_POJ 八数码_poj”指的是一个与编程竞赛网站POJ(Problem Set Algorithm)相关的项目,具体是针对3131号问题的解决方案,该问题涉及到了八数码游戏。八数码游戏,又称滑动拼图,是一个经典的...

    POJ题目简单分类(ACM)

    - **凸包**:找到包含所有点的最小凸多边形,如poj2187。 这些知识点是ACM竞赛中常见的主题,掌握了这些,可以有效提升解决算法问题的能力。对于初级选手,可以从基础算法开始,逐步挑战更复杂的图算法和数据结构...

    POJ2002-Squares

    在"POJ2002-Squares"这个问题中,参赛者可能需要编写一个程序来处理与正方形相关的数学问题。这可能涉及到计算和处理大量正方形,例如找出一个范围内的所有完全平方数,或者计算不同大小正方形覆盖区域的重叠部分。...

    jihe.rar_2289_POJ 3714_poj3714_poj3714 Ra_visual c

    标题中的"jihe.rar_2289_POJ 3714_poj3714_poj3714 Ra_visual c" 提到了一个压缩文件,可能包含有关编程竞赛或算法解决的资源,特别是与POJ(Problem On Judge)平台上的问题3714相关的。"Ra_visual c"可能指的是...

    POJ1159-Palindrome

    【描述】"北大POJ1159-Palindrome 解题报告+AC代码" 暗示了解决这道问题的方法和通过验证的源代码。解题报告通常会包含问题分析、算法设计、代码实现以及可能的优化策略。AC(Accepted)代码意味着提交的代码已经...

Global site tag (gtag.js) - Google Analytics