hdu 1348 Wall (凸包模板)

/*
 题意:

 求得n个点的凸包,然后求与凸包相距l的外圈的周长。

 答案为n点的凸包周长加上半径为L的圆的周长

*/
# include <stdio.h>
# include <math.h>
# include <string.h>
# include <algorithm>
using namespace std;
# define PI acos(-1.0)
struct node
{
    int x;
    int y;
};
node a[1010],res[1010];
bool cmp(node a1,node a2)
{
    if(a1.x==a2.x)
        return a1.y<a2.y;
    return a1.x<a2.x;
}
int cross(node a1,node a2,node a3)
{
    return (a1.x-a3.x)*(a2.y-a3.y)-(a2.x-a3.x)*(a1.y-a3.y);
}
int convex(int n)//求凸包上的点
{
    int m=0,i,j,k;
    sort(a,a+n,cmp);
     //求得下凸包,逆时针
    //已知凸包点m个,如果新加入点为i,则向量(m-2,i)必定要在(m-2,m-1)的逆时针方向才符合凸包的性质
    //若不成立,则m-1点不在凸包上。
    for(i=0;i<n;i++)
    {
        while(m>1&&cross(res[m-1],a[i],res[m-2])<=0)
            m--;
        res[m++]=a[i];
    }
    k=m;
    //求得上凸包
    for(i=n-2;i>=0;i--)
    {
        while(m>k&&cross(res[m-1],a[i],res[m-2])<=0)
            m--;
        res[m++]=a[i];
    }
    if(n>1)
        m--;
    return m;
}
double length(node a1,node a2)
{
    return sqrt(1.0*(a1.x-a2.x)*(a1.x-a2.x)+(a1.y-a2.y)*(a1.y-a2.y));
}
int main()
{
    int t,n,i,L,m;
    while(~scanf("%d",&t))
    {
        while(t--)
        {
            scanf("%d%d",&n,&L);
            for(i=0;i<n;i++)
                scanf("%d%d",&a[i].x,&a[i].y);
            m=convex(n);
            double ans=0;
            for(i=1;i<m;i++)
                ans+=length(res[i],res[i-1]);
            ans+=length(res[0],res[m-1]);
            ans+=2*PI*L;
            printf("%.0lf\n",ans);
            if(t)
                printf("\n");
        }
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

时间: 07-23

hdu 1348 Wall (凸包模板)的相关文章

hdu 1348 Wall (凸包)

Wall Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 3139    Accepted Submission(s): 888 Problem Description Once upon a time there was a greedy King who ordered his chief Architect to build a w

POJ 1113 || HDU 1348: wall(凸包问题)

传送门: POJ:点击打开链接 HDU:点击打开链接 下面是POJ上的题: Wall Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 29121   Accepted: 9746 Description Once upon a time there was a greedy King who ordered his chief Architect to build a wall around the King's cast

hdu 1348 (凸包求周长)

链接:http://acm.hdu.edu.cn/showproblem.php?pid=1348 Wall Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 3229    Accepted Submission(s): 919 Problem Description Once upon a time there was a greedy

POJ 3528 hdu 3662 三维凸包模板题

POJ 3528题:http://poj.org/problem?id=3528 HDU 3662:http://acm.hdu.edu.cn/showproblem.php?pid=3662 一个是求三维凸包面数,一个是求三维凸包表面积,都是很裸的. 贴代码: #include<stdio.h> #include<algorithm> #include<string.h> #include<math.h> #include<stdlib.h>

hdu 1348 Wall(凸包模板题)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1348 Wall Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 3386    Accepted Submission(s): 968 Problem Description Once upon a time there was a gre

HDU 1348 Wall 【凸包】

<题目链接> 题目大意: 给出二维坐标轴上 n 个点,这 n 个点构成了一个城堡,国王想建一堵墙,城墙与城堡之间的距离总不小于一个数 L ,求城墙的最小长度,答案四舍五入. 解题分析: 求出这些点所围成的凸包,然后所围城墙的长度就为 该凸包周长 + 以该距离为半径的圆的周长.具体证明如下: 下面的模板还没有整理好 Graham 凸包算法 #include<iostream> #include<cstdio> #include<cmath> #include&

POJ 1113 - Wall 凸包模板

此题为凸包问题模板题,题目中所给点均为整点,考虑到数据范围问题求norm()时先转换成double了,把norm()那句改成<vector>压栈即可求得凸包. 初次提交被坑得很惨,在GDB中可以完美运行A掉,到OJ上就频频RE(此处应有黑人问号) 后来发现了问题,原因是玩杂耍写了这样的代码 struct point { int x, y; point (){ scanf("%d%d", &x, &y); } ... }pt[MAXN]; 于是乎,在swap

poj 1113 Wall (凸包模板题)

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

POJ - 1113 Wall (凸包模板题)

原题链接 模板题,直接说思路. 思路: 要求一距离凸包为 L 的图形的周长,即为 凸包周长+L为半径的圆周长 ,直接用 Graham 求一次凸包即可. 1 /* 2 * @Author: windystreet 3 * @Date: 2018-08-02 20:41:25 4 * @Last Modified by: windystreet 5 * @Last Modified time: 2018-08-02 22:30:59 6 */ 7 #include <stdio.h> 8 #inc