http://acm.hdu.edu.cn/showproblem.php?pid=1392

题目大意:

  二维平面给定n个点,用一条最短的绳子将所有的点都围在里面,求绳子的长度。

解题思路:

  凸包的模板。凸包有很多的算法。这里用Adrew。

  注意这几组测试数据

  1

  1 1

  3

  0 0

  1 0

  2 0

  输出数据

  0.00

  2.00

 #include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std; #define MAXN 100+10 struct Point{
double x, y; Point(double x = , double y = ): x(x), y(y){} void scan(){
scanf("%lf %lf", &x, &y);
}
}; typedef Point Vector; Vector operator - (Vector A, Vector B){
return Vector(A.x - B.x, A.y - B.y);
} double dot(Vector A, Vector B){//点乘
return A.x * B.x + A.y * B.y;
}
double length(Vector A){//向量模
return sqrt(dot(A, A));
}
double cross(Vector A, Vector B){//叉乘
return A.x * B.y - A.y * B.x;
} int n;
Point p[MAXN], stack[MAXN]; bool input(){
scanf("%d", &n);
if(n == ) return false;
for(int i = ; i < n; ++i){
p[i].scan();
}
return true;
} bool cmp(Point A, Point B){
return A.x < B.x || (A.x == B.x && A.y < B.y);
} int convex_hull(){//Adrew算法 求凸包
sort(p, p + n, cmp); int m = ;
for(int i = ; i < n; ++i){
while(m > && cross(stack[m - ] - stack[m - ], p[i] - stack[m - ]) <= ) --m;
stack[m ++] = p[i];
}
int k = m;
for(int i = n - ; i >= ; --i){
while(m > k && cross(stack[m - ] - stack[m - ], p[i] - stack[m - ]) <= ) --m;
stack[m ++] = p[i];
}
if(n > ) --m;
return m;
} void solve(){
n = convex_hull();
if(n == ){//当只有一个点时,绳子长度为0
puts("0.00");
return ;
}
if(n == ){//当只有两个点时,绳子长度为两点之间的长度
printf("%.2lf\n", length(stack[] - stack[]));
return ;
}
double ans = ;//绳子的累加长度
stack[n] = stack[];//为了算第n点到第1点的距离
for(int i = ; i < n; ++i){
ans += length(stack[i] - stack[i + ]);
}
printf("%.2lf\n", ans);
} int main(){
while(input()){
solve();
}
return ;
}

最新文章

  1. javaMail
  2. dom4j 读取xml
  3. IIS7.5下启用asp父级路径
  4. 一步步学Mybatis-以接口操作的方式编程(2)
  5. [leetcode] Path sum路径之和
  6. A9系统时钟用外部
  7. Android切换页面--setContentView
  8. 如何有效抓取SQL Server的BLOCKING信息
  9. hibernate异常:org.hibernate.NonUniqueObjectException
  10. python enumerate 枚举函数用法
  11. IOS开发之XCode学习009:UIViewController使用
  12. 2018-计算机系机试(第二批)-A-最大数
  13. MapReduce(二)
  14. LibreOJ #6001. 「网络流 24 题」太空飞行计划 最大权闭合图
  15. smarty学习——编写扩展
  16. SourceTree下载 及使用
  17. yum安装方式的php,切换NTS为ZTS版本
  18. matlab中图片数据类型转换uint8与double
  19. 【prometheus】学习第一篇——prometheus
  20. 主键约束 primary key

热门文章

  1. c实现的list
  2. 第四步 使用 adt-eclipse 打包 Cordova (3.0及其以上版本) + sencha touch 项目
  3. 监控redis服务器执行的命令--类似于tomcat的local-access.log
  4. 4606: [Apio2008]DNA
  5. 完美解决Android SDK Manager无法更新
  6. 复杂度O(n)计算
  7. CAT偶现NPE的问题
  8. linux 命令行常用快捷键
  9. return 通过文件后缀名得到的函数字符串
  10. HDU 2476 String painter(区间DP)