注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 1348  

2012-10-27 16:29:13|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
题意:要在城堡外面建立城墙,要求城堡任意点的距离与城墙的距离>=r,求所建城墙的周长最短。
思路:该题是凸包问题,墙的周长 = 凸包的周长 + 以r为半径的圆的周长。
ps:第一次做凸包问题,模板题,Graham算法做模板

/*
* hdu 1348
* fudq.cpp
*
* Created on: 2012-10-27
*/
#include<algorithm>
#include<stdio.h>
#include<string>
#include<string.h>
#include<math.h>
#include<queue>
#include<map>
#include<iostream>
using namespace std;
#define N 1010
const double PI=acos(-1.0);
struct point{double x,y,angel;}pnt[N],res[N];
int top,n;

double dis(point a,point b)//求距离
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

bool mult(point sp,point ep,point op)//叉乘
{
return (sp.x-op.x)*(ep.y-op.y) >= (ep.x-op.x)*(sp.y-op.y);
}

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.angel == b.angel)
{
if (a.x == b.x)
return a.y > b.y;
return a.x > b.x;
}
return a.angel < b.angel;
}

void graham()
{
//pnt为点集,n为点的个数,res为凸包点集,top为凸包个数
int i;
sort(pnt,pnt+n,cmp1);//找到左下角的pnt[0]
//找相对于pnt[0]的极角,并把除了pnt[0]以外的点按照极角排序
for(i=1;i<n;i++)
pnt[i].angel=atan2(pnt[i].y-pnt[0].y,pnt[i].x-pnt[0].x);
sort(pnt+1,pnt+n,cmp2);
//Graham
res[0]=pnt[0];res[1]=pnt[1];res[2]=pnt[2];
top=3;
for(i=3;i<n;i++)
{
while(top > 2 && mult(res[top-2],res[top-1],pnt[i])<=0)
top--;
res[top++]=pnt[i];
}
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
#endif
int T,i,flag=0;
double r,ans;
scanf("%d",&T);
while(T--)
{
scanf("%d%lf",&n,&r);
for(i=0;i<n;i++)
scanf("%lf%lf",&pnt[i].x,&pnt[i].y);
graham();
ans=0;
for(i=0;i<top-1;i++)
ans+=dis(res[i],res[i+1]);
ans+=dis(res[top-1],res[0]);
ans+=2*PI*r;
if(flag==1)
printf("\n");
printf("%.0lf\n",ans);
flag=1;
}
return 0;
}


  评论这张
 
阅读(280)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018