POJ 1113 - Wall


  • POJ 1113 - Wall
  • Time: 1000MS
  • Memory: 10000K
  • 难度: 初级
  • 分类: 凸包

问题描述

给定多边形城堡的n个顶点,绕城堡外面建一个围墙,围住所有点,并且墙与所有点的距离至少为L,求这个墙最小的长度。

解题思路

推导公式(1)城堡围墙长度最小值 = 城堡顶点坐标构成的散点集的凸包总边长 + 半径为L的圆周长

由于数据规模较大,必须用GrahamScan Algorithm构造凸包(详细的算法可以参考我的 [POJ2187](.//Memory Time
//244K 63MS

#include
#include
#include
using namespace std;

const int inf=10001;
const double pi=3.141592654;

typedef class
{
public:
int x,y;
}point;

/AB距离平方/

int distsquare(point A,point B)
{
return (B.x-A.x)(B.x-A.x)+(B.y-A.y)(B.y-A.y);
}

/AB距离/

double distant(point A,point B)
{
return sqrt((double)((B.x-A.x)(B.x-A.x)+(B.y-A.y)(B.y-A.y)));
}

/叉积计算/

int det(int x1,int y1,int x2,int y2)
{
return x1y2-x2y1;
}

int cross(point A,point B,point C,point D)
{
return det(B.x-A.x,B.y-A.y,D.x-C.x,D.y-C.y);
}

/快排判断规则/

point* s;
int cmp(const void* pa,const void* pb)
{
point* a=(point*)pa;
point* b=(point*)pb;

int temp=cross(*s,*a,*s,*b);
if(temp>0)
    return -1;
else if(temp==0)
    return distsquare(*s,*b)-distsquare(*s,*a);
else
    return 1;

}

int main(int i,int j)
{
int N,L;
while(cin>>N>>L)
{
/Input/

    point* node=new point[N+1];

    int min_x=inf;
    int fi;
    for(i=1;i<=N;i++)
    {
        cin>>node[i].x>>node[i].y;

        if(min_x > node[i].x)
        {
            min_x = node[i].x;
            fi=i;
        }
        else if(min_x == node[i].x)
            if(node[fi].y > node[i].y)
                fi=i;
    }

    /*Quicksort the Vertex*/

    node[0]=node[N];
    node[N]=node[fi];
    node[fi]=node[0];

    s=&node[N];
    qsort(node+1,N,sizeof(point),cmp);

    /*Structure Con-bag*/

    int* bag=new int[N+2];
    bag[1]=N;
    bag[2]=1;
    int pb=2;
    for(i=2;i<=N;)
        if(cross(node[ bag[pb-1] ],node[ bag[pb] ],node[ bag[pb] ],node[i]) >= 0)
            bag[++pb]=i++;
        else
            pb--;

    /*Compute Min-length*/

    double minlen=0;
    for(i=1;i<pb;i++)
        minlen+=distant(node[ bag[i] ],node[ bag[i+1] ]);

    minlen+=2*pi*L;

    cout<<fixed<<setprecision(0)<<minlen<<endl;

    delete node;
    delete bag;
}
return 0;

}


------


## 相关资料

- [北大 ACM - POJ 试题分类](https://exp-blog.com/algorithm/poj-shi-ti-fen-lei/)
- [北大 POJ 题库(官网在线)](http://poj.org/)
- [北大 POJ 题库(离线版)](https://github.com/lyy289065406/POJ-Solving-Reports/doc/POJ%E7%A6%BB%E7%BA%BF%E7%89%88%E9%A2%98%E7%9B%AE.chm)
- [POJ封面书《程序设计导引及在线实践》](https://github.com/lyy289065406/POJ-Solving-Reports/doc/程序设计导引及在线实践.pdf)
- [ACM 资料](https://lyy289065406.github.io/articles/tags/ACM/)

文章作者: EXP
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 EXP !
 上一篇
POJ 1724 - ROADS POJ 1724 - ROADS
POJ 1724 - ROADS Time: 1000MS Memory: 65536K 难度: 中级 分类: 搜索 问题描述给定一个图,图中每条路都有 路长Length 和 过路费Toll 两个参数,一条路连接两个城市,任意两个城市之
2011-08-11
下一篇 
POJ 1837 - Balance POJ 1837 - Balance
POJ 1837 - Balance Time: 1000MS Memory: 30000K 难度: 初级 分类: 背包 问题描述有一个天平,天平左右两边各有若干个钩子,总共有C个钩子,有G个钩码,求将钩码全部挂到钩子上使天平平衡的方法
2011-08-08
  目录