专栏首页小L的魔法馆POJ 1113--Wall(计算凸包)

POJ 1113--Wall(计算凸包)

Wall Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 40363 Accepted: 13754 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

结果四舍五入就可以了

  • 不是直接求凸包,围住城堡的所需的最小距离,这个是凸包的长度,但是建造的围墙和城堡之间还有一个距离L,所以所求周长比凸包长度要多几段圆弧,所有圆弧的角度和为360°360°360°,所以再加上一个半径为L的圆周长即为所求.
  • 步进法
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
using namespace std;
const int MAX = 5005;
const double PI = acos(-1.0);
typedef struct point {
    double x;
    double y;
    point() {

    }
    point(double a, double b) {
        x = a;
        y = b;
    }
    point operator -(const point &b)const {     //返回减去后的新点
        return point(x - b.x, y - b.y);
    }
    double operator *(const point &b)const {    //点乘
        return x*b.x + y*b.y;
    }
}point;
double dist(point p1, point p2) {       //返回平面上两点距离
    return sqrt((p1 - p2)*(p1 - p2));
}
int n, c, w, ans[MAX], num, sd[MAX], ta, stk[MAX], tp1, tp2;
point x[MAX];
bool cmp(point a, point b) { return a.y < b.y || a.y == b.y && a.x < b.x; } //先按y,再按x从小排序
bool cmulti(point p1, point p2, point p3) {  //判断p1p0和p2p0的关系,<0,p1p0在p2p0的逆时针方向
    return ((p3.x - p1.x)*(p2.y - p1.y) - (p2.x - p1.x)*(p3.y - p1.y))<0;
}
void Jarvis() {
    ta = num = 0;
    sd[ta++] = 0, sd[ta++] = 1;
    sort(x, x + n, cmp);
    for (int i = 2; i < n; i++) {
        while (ta > 1 && !cmulti(x[sd[ta - 1]], x[sd[ta - 2]], x[i]))//不是外侧点则回溯,且不取内部点
            ta--;
        sd[ta++] = i;
    }
    for (int j = 0; j < ta; j++) {
        ans[num++] = sd[j];
    }
    ta = 0;
    sd[ta++] = n - 1;
    sd[ta++] = n - 2;
    for (int i = n - 3; i >= 0; i--) {
        while (ta > 1 && !cmulti(x[sd[ta - 1]], x[sd[ta - 2]], x[i]))
            ta--;
        sd[ta++] = i;
    }
    for (int j = 0; j < ta; j++) {
        ans[num++] = sd[j];
    }
}
int main() {
    scanf("%d%d", &n, &c);
    for (int i = 0; i < n; i++) {
        scanf("%lf%lf", &x[i].x, &x[i].y);
    }
    Jarvis();
    double res1 = 0;
    for (int i = 0; i < num - 1; i++) {
        res1 += dist(x[ans[i]], x[ans[i + 1]]);
    }
    res1 += 2 * PI * c;
    printf("%.0f\n", res1);
    return 0;
}
  • 用Gamham-scan重写了一下vo(*  ̄ ▽  ̄ *)ov
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
using namespace std;
const int MAX = 5005;
const double PI = acos(-1.0);
typedef struct point {
    double x;
    double y;
    point() {

    }
    point(double a, double b) {
        x = a;
        y = b;
    }
    point operator -(const point &b)const {     //返回减去后的新点
        return point(x - b.x, y - b.y);
    }
    double operator *(const point &b)const {    //点乘
        return x*b.x + y*b.y;
    }
}point;
double dist(point p1, point p2) {       //返回平面上两点距离
    return sqrt((p1 - p2)*(p1 - p2));
}
int n, res[MAX];    //ans为凸包点集坐标,n为点的个数,sd为临时坐标。
int top = 1;
point p[MAX];       //x存放凸包点集
bool cmp(point a, point b) {
    if (a.y == b.y) return a.x < b.x;
    return a.y < b.y;
}
bool multi(point p1, point p2, point p0) {  //判断p1p0和p2p0的关系,<0,p1p0在p2p0的逆时针方向,>0,p1p0在p2p0的顺时针方向
    return (p1.x - p0.x)*(p2.y - p0.y) >= (p2.x - p0.x)*(p1.y - p0.y);
}
void Graham(int n) {
    int i, len; //top模拟栈顶
    sort(p, p + n, cmp);
    //少于3个点也就没有办法形成凸包
    if (n == 0)return; res[0] = 0;
    if (n == 1)return; res[1] = 1;
    if (n == 2)return; res[2] = 2;
    for (i = 2; i < n; i++) {
        while (top&&multi(p[i], p[res[top]], p[res[top - 1]]))  //如果当前这个点和栈顶两个点构成折线右拐了,就回溯到上一个点
            top--;                                              //弹出栈顶
        res[++top] = i;                                         //否则将这个点入栈
    }
    len = top;
    res[++top] = n - 2;
    for (int i = n - 3; i >= 0; i--) {
        while (top!=len&&multi(p[i], p[res[top]], p[res[top - 1]]))
            top--;
        res[++top] = i;
    }
}
int main() {
    int c;
    scanf("%d%d", &n, &c);
        for (int i = 0; i < n; i++) {
            scanf("%lf%lf", &p[i].x, &p[i].y);
        }
        Graham(n);
        double res1 = 0;
        for (int i = 0; i < top; i++) {
            res1 += dist(p[res[i]], p[res[i + 1]]);
        }
        res1 += 2 * PI * c;
        printf("%.0f\n", res1);
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Linux 的启动流程

    前阵子,分享了一篇计算机是如何启动的?的文章,主要探讨BIOS和主引导记录的作用。

    帅地
  • 在后台运行相应程序windows与linux下。

    nohup python -u test.py > test.log 2>&1 &

    学到老
  • linux 下的 CentOS 6.8 安装mongodb

    [root@xxxx local]# curl -o mongodb-linux-x86_64-3.4.6.tgz https://fas tdl.mongod...

    学到老
  • 五种I/O模型和Java NIO源码分析

      最近在学习Java网络编程和Netty相关的知识,了解到Netty是NIO模式的网络框架,但是提供了不同的Channel来支持不同模式的网络通信处理,包括同...

    remcarpediem
  • Windows成“弃子”,Linux终上位?

    时光倒退二十年,彼时不可一世的微软将开源软件视为眼中钉肉中刺,甚至吐槽其是知识产权的癌症。如今,从“爱 Linux“到豪掷 75 亿美元收购 GitHub,微软...

    三哥
  • IoT中的Linux选择

    在物联网的设备设计中,从低成本和低功耗的角度看,Android肯定比不过嵌入式Linux。但在选择用于部署Linux的发行版本时,却一直饱受困扰。

    半吊子全栈工匠
  • 从未如此了解过Linux

    操作系统内核是指大多数操作系统的核心部分。它由操作系统中用于管理存储器、文件、外设和系统资源的那些部分组成。操作系统内核通常运行进程,并提供进程间的通信。 Li...

    CC老师
  • c程序协程的实现和openssl 1.x版本的应用

    一段代码能否把机器硬件性能发挥到极致,我们通常用cpu和IO利用率(本地存储io和网络io)来衡量。

    mariolu
  • linux (ubantu)安装最新版python3.6,以及直接安装anaconda

    版本下载(清华镜像):wget https://mirrors.tuna.tsinghua.edu.cn/anaconda/archive/Anaconda3-...

    学到老
  • 对开源的认知

    没有开源软件,现在的互联网根本无法存在,开源的历史可以追溯到ARPANET建立。开源在今天已经不再是一个时髦的词了,对于互联网的开发者来说,它现在就像空气和水一...

    半吊子全栈工匠

扫码关注云+社区

领取腾讯云代金券