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

东月之神

在单纯的观念里面,生命就容易变得比较深刻!

 
 
 

日志

 
 
关于我

别驻足,梦想要不停追逐,别认输,熬过黑暗才有日出,要记住,成功就在下一步,路很苦,汗水是最美的书!

网易考拉推荐

zju1453 Surround the Trees  

2010-05-08 21:57:41|  分类: ACM |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
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.

zju1453 Surround the Trees - 东月之神 - 东月之神

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

 

题目大意就是把所有的点都包围住。用了计算几何的凸包。考虑下一个点的情况就可以了。

代码:

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

struct Point
{
 double x, y;
};
int n;
inline double dis(Point p1, Point p2)
{
 return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}

inline double cross(Point p1, Point p2, Point p3)
{
 return (p2.x-p1.x)*(p3.y-p1.y) - (p2.y-p1.y)*(p3.x-p1.x);
}

inline bool comp(const Point &p1, const Point &p2)
{
 if(p1.y < p2.y) return true;
 if(p1.y > p2.y) return false;
 if(p1.x < p2.x) return true;
}

inline void getconvexhull(Point p1[], Point p2[], int &top)
{
 sort(p1, p1 + n, comp);
 int i;
 top = 0;
 p2[top++] = p1[0];
 p2[top++] = p1[1];
 for(i = 2; i < n; i++)
 {
  while(top >= 2 && cross(p2[top-2], p2[top-1], p1[i]) <= 0)
   --top;
  p2[top++] = p1[i];
 }
 int r = top;
 for(i = n-2; i >= 0; i--)
 {
  while(top > r && cross(p2[top-2], p2[top-1], p1[i]) <= 0)
   --top;
  if(i != 0)
   p2[top++] = p1[i];
 }
}
int main()
{
 int m, i; 
 while(scanf("%d", &n) != EOF && n)
 {
  Point p1[105], p2[105];
  for(i = 0; i < n; i++)
   scanf("%lf%lf", &p1[i].x, &p1[i].y);
  if(n == 1){printf("0.00\n"); continue;}
  getconvexhull(p1, p2, m);
  double ans = 0.0;
  for(i = 0; i < m - 1; i++)
   ans += dis(p2[i], p2[i+1]);
  ans += dis(p2[0], p2[m-1]);
  printf("%.2lf\n", ans);
 }
return 0;
}

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

历史上的今天

评论

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

页脚

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