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

告别迷茫

梦想与现实的差距,就是我们生活的意义。因为我们有差距,我们才会一直积累,在努力。

 
 
 

日志

 
 

hdu 1392 Surround the Trees 简单的凸包的问题  

2014-04-13 23:42:42|  分类: 计算几何 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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.


hdu  1392  Surround the Trees  简单的凸包的问题 - 983433479 - jet sky


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   |   We have carefully selected several
similar problems for you:  1086 2150 1348 1147 1558 

 

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;


struct node
{
int x,y;
}a[110],stack1[110];//a 输入 stack 压站


double distan(node a,node b)//长度
{
return (double)sqrt((a.x-b.x)*(a.x-b.x)*1.0+(a.y-b.y)*(a.y-b.y)*1.0);
}
double across(node a,node n1,node n2)// 为正时 "左转"
{
return (n1.x-a.x)*(n2.y-a.y) - (n1.y-a.y)*(n2.x-a.x);
}
bool cmp(node a1,node b1)//比较大小 差集大的 往左 相等 则距离大的就是我们要找的
{
double k=across(a[0],a1,b1);
if(k>0) return true;
else if (k==0&&distan(a[0],a1)<distan(a[0],b1))
{
return true;
}
else return false;
}
void anglesort(int n)//找最下面的我们的Y最小,Y相当X小的;
{
int i,k=0;
node temp;
for(i=1;i<n;i++)
{
if(a[i].y<a[k].y||(a[i].y==a[k].y&&a[i].x<a[k].x))
k=i;
}
temp=a[0];
a[0]=a[k];
a[k]=temp;
sort(a+1,a+n,cmp);
}
void Graham(int n)
{
anglesort(n);
int i,head;
double sum=0;
a[n]=a[0];//形成圆的形状,最后的压站好处理;
stack1[0]=a[0];//压站
stack1[1]=a[1];
stack1[2]=a[2];
head=2;
for(i=3;i<=n;i++)
{
while(head>=2 && (across(stack1[head-1],stack1[head],a[i])<=0)) head--;//如果我们的进入了没有满足向左偏则我们的把他们拿出来

stack1[++head]=a[i];//压入下一个元素
}
for(i=0;i<head;i++)
{
sum+=distan(stack1[i],stack1[i+1]);
// printf("%lf ",sum);
}
printf("%.2lf\n",sum);

}
int main()
{
int i,n;
while(scanf("%d",&n),n)
{
for(i=0;i<n;i++)
{
scanf("%d%d",&a[i].x,&a[i].y);
}
if(n==1)
{
printf("0.00\n");
continue;
}
if(n==2)
{
printf("%.2lf\n",distan(a[0],a[1]));
continue;
}
Graham(n);

}
return 0;
}



#include<iostream>
#include<stdio.h>
#include<string.h>
#include<queue>
#include<stack>
#include<math.h>
#include<algorithm>
using namespace std;
struct Tree {double x,y;};
Tree tree[110],stan;
stack<Tree> sta;
queue<Tree> que;
int cmp(Tree t1,Tree t2)
{
double x1=t1.x-stan.x,y1=t1.y-stan.y;
double x2=t2.x-stan.x,y2=t2.y-stan.y;
return x1*y2-x2*y1>0;
}
inline bool turnright(Tree& t1,Tree& t2,Tree& t3)
{
double x1=t2.x-t1.x,y1=t2.y-t1.y;
double x2=t3.x-t2.x,y2=t3.y-t2.y;
if(x1*y2-x2*y1<0) return true;
return false;
}
inline double Dis(Tree& t1,Tree& t2)
{
double x=t1.x-t2.x;
double y=t1.y-t2.y;
return sqrt(x*x+y*y);
}
double Find()
{
double ans=0;
Tree temp,temp1,temp2;
while(!que.empty())
{
temp=que.front();
que.pop();
temp1=sta.top();
sta.pop();
temp2=sta.top();
sta.push(temp1);
while(turnright(temp2,temp1,temp))
{
sta.pop();
temp1=sta.top();
sta.pop();
temp2=sta.top();
sta.push(temp1);
}
sta.push(temp);
}
temp1=sta.top();
sta.pop();
temp2=sta.top();
sta.push(temp1);
if(turnright(temp2,temp1,stan))
sta.pop();
temp2=temp=sta.top(); //printf("%.2lf,%.2lf\n",temp.x,temp.y);
sta.pop();
while(!sta.empty())
{printf("%.2lf,%.2lf\n",temp.x,temp.y);
temp1=sta.top();
sta.pop();
ans+=Dis(temp,temp1);
temp=temp1;//printf("%.2lf,%.2lf\n",temp.x,temp.y);
}
return ans+=Dis(temp,temp2);;
}
int main()
{
int n,i,t;
double y;
Tree temp;
//FILE *fp=fopen("F://guan.txt","r");
//while(fscanf(fp,"%d",&n)!=EOF)
while(scanf("%d",&n)!=EOF)
{
if(n<1) break;
for(i=0;i<n;i++)
{
//fscanf(fp,"%lf%lf",&tree[i].x,&tree[i].y);
scanf("%lf%lf",&tree[i].x,&tree[i].y);
if(!i)
{
y=tree[i].y;
t=i;
}
else if(tree[i].y<y)
{
y=tree[i].y;
t=i;
}
}
if(n==1)
{
printf("%.2lf\n",0);
continue;
}
if(n==2)
{
double falseans=Dis(tree[0],tree[1]);
printf("%.2lf\n",falseans);
continue;
}
temp=tree[0];
tree[0]=tree[t];
tree[t]=temp;
stan=tree[0];
sort(tree+1,tree+n,cmp);
for(i=0;i<n;i++)
{
if(i<2)
sta.push(tree[i]);
else
que.push(tree[i]);
//printf("%lf,%lf\n",tree[i].x,tree[i].y);
}
double ans=Find();
printf("%.2lf\n",ans);

}
//fclose(fp);
return 0;
}

同学的代码 发型编译
  评论这张
 
阅读(1)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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