`

HDU 1392 Surround the Trees .

阅读更多

Surround the Trees

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3223    Accepted Submission(s): 1230

Problem Description
There are a lot of trees in an area. A peasant wants to buy a rope to surround all these trees. So at first he must know the minimal required length of the rope. However, he does not know how to calculate it. Can you help him?
The diameter and length of the trees are omitted, which means a tree can be seen as a point. The thickness of the rope is also omitted which means a rope can be seen as a line.



There are no more than 100 trees.
 

 

Input
The input contains one or more data sets. At first line of each input data set is number of trees in this data set, it is followed by series of coordinates of the trees. Each coordinate is a positive integer pair, and each integer is less than 32767. Each pair is separated by blank.

Zero at line for number of trees terminates the input for your program.
 

 

Output
The minimal length of the rope. The precision should be 10^-2.
 

 

Sample Input
9 12 7 24 9 30 5 41 9 80 7 50 87 22 9 45 1 50 7 0
 

 

Sample Output
243.06
 

 

Source
 

 

Recommend
Ignatius.L
 
凸包水题直接GramhamScan可以过,不过要注意n < 3两个特例。
果断贴代码:
4285845 2011-07-29 12:51:30 Accepted 1392 78MS 272K 1631 B C++ 10SGetEternal{(。)(。)}!
#include <iostream>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define MAXI 111

class point
{
public :
    double x, y;

    point(double tx = 0.0, double ty = 0.0)
    {
        x = tx;
        y = ty;
    }

    double dis() 
    { 
        return sqrt(pow(x, 2) + pow(y, 2)); 
    };

    point operator - (point &o)
    {
        return point(x - o.x, y - o.y);
    }

    double operator * (point &o) 
    {
        return x * o.y - y * o.x;
    }
}ps[MAXI];

vector<point> chul;
int n;

bool cmp(point &a, point &b)
{
    double cp = (ps[0] - a) * (b - a);

    if (cp == 0) return (a - ps[0]).dis() > (b - ps[0]).dis();
    else  if (cp < 0)  return 1;
    return 0;
}

double GHS()
{
    int i, idm;
    double tsu = 0.0;

    for (idm = i = 0; i < n; i++)
        if (ps[i].y == ps[idm].y && ps[i].x < ps[idm].x || ps[i].y < ps[idm].y)
            idm = i;
    swap(ps[idm], ps[0]);
    sort(ps + 1, ps + n, cmp);
    chul.clear();
    chul.push_back(ps[0]);
    chul.push_back(ps[1]);
    for (i = 2; (ps[0] - ps[1]) * (ps[i] - ps[1]) == 0; i++);
    chul.push_back(ps[i]);
    for (i++; i < n; i++)
    {
        while ((chul[chul.size() - 2] - chul[chul.size() - 1]) * (ps[i] - chul[chul.size() - 1]) >= 0)
            chul.pop_back();
        chul.push_back(ps[i]);
    }
    for (i = 0; i < chul.size(); i++)
        tsu += (chul[(i + 1) % chul.size()] - chul[i]).dis(); 

    return tsu;
}

int main()
{
    int i;

    while (scanf("%d", &n), n)
    {
        for (i = 0; i < n; i++)
            scanf("%lf%lf", &ps[i].x, &ps[i].y);
        if (n == 2) printf("%.2lf\n", ps[1] - ps[0]);
        else if (n ==  1) printf("0\n");
        else printf("%.2lf\n", GHS());
    }

    return 0;
}

 Thanks……

分享到:
评论

相关推荐

    杭电操作系统实验 HDU操作系统实验.zip

    杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU...

    大学期间操作系统实验-HDU操作系统实验.zip

    HDU操作系统实验.zip大学期间操作系统实验-HDU操作系统实验.zip大学期间操作系统实验-HDU操作系统实验.zip大学期间操作系统实验-HDU操作系统实验.zip大学期间操作系统实验-HDU操作系统实验.zip大学期间操作系统实验-...

    hdu_acm_1084.rar_ACM_HDU10_acm10_hdu_hdu 1084

    【标题】"hdu_acm_1084.rar_ACM_HDU10_acm10_hdu_hdu 1084" 提供的是一个关于杭电(HDU)ACM竞赛第1084题的解决方案。该题目可能是在编程竞赛中常见的算法问题,而ACM(国际大学生程序设计竞赛)是全球知名的编程...

    HDU-GO v19.1225.2.zip

    【HDU-GO v19.1225.2.zip】是一个针对杭州电子科技大学(HDU)选课系统的浏览器插件,版本号为v19.1225.2。这个插件的主要功能是优化和提升学生在进行网络选课时的体验,它可能包含了增强界面、自动化操作、数据解析...

    HDU-ACM_java.rar_hdu

    【标题】"HDU-ACM_java.rar" 是一个针对杭州电子科技大学(HDU)ACM竞赛的资源压缩包,其中包含的是使用Java语言编写的算法解决方案。这个压缩包主要面向那些参与或准备参与ACM国际大学生程序设计竞赛(ICPC)的参赛...

    HDU-2000-2099.zip_hdu2000

    【标题】"HDU-2000-2099.zip_hdu2000" 是一个包含杭电(Hangzhou Dianzi University)ACM竞赛题目解题报告的压缩包,覆盖了编号从2000到2099的题目。这个资源对于学习算法、提高编程技巧以及准备ACM/ICPC(国际大学...

    HDU-2000-2099.rar_hdu

    HDU(杭州电子科技大学在线评测系统)是一个知名的编程竞赛平台,为编程爱好者提供了大量的算法题目进行练习和比赛。这个名为"HDU-2000-2099.rar_hdu"的压缩包包含了该平台从2000到2099共100道题目的源代码。这些...

    hdu1392 代码

    凸包经典入门,求凸包周长.00000000000000000000000

    个人数据库原理课程设计的期末作业留档_HDU-suspermarket_sys.zip

    个人数据库原理课程设计的期末作业留档_HDU-suspermarket_sys

    ACM HDU题目分类

    ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...

    hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj

    【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...

    hangdianACM.rar_hangdiana_hdu acm_www.hangdianacm_杭电

    这个压缩文件包含的是作者个人提交并解决的ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)题目,这些题目来源于HDU的在线编程平台。 【描述】"杭电的一些acm题目,都是我自己一个一...

    hdu5102.zip_K.

    标题中的"hdu5102.zip_K."暗示这是一个与编程竞赛相关的题目,通常在HDU(杭州电子科技大学)在线判题系统中出现。这个题目可能是一个编程挑战,要求参赛者解决一个特定的问题,并提交源代码以供自动评判。"K."可能...

    HDU-ACM课件.rar

    HDU-ACM课件.rar 是一个专门为编程竞赛爱好者准备的资源包,主要涵盖了ACM(国际大学生程序设计竞赛)中常见的算法知识。这个压缩包包含了一系列与算法相关的主题,旨在帮助初学者理解和掌握基础及进阶算法。下面将...

Global site tag (gtag.js) - Google Analytics