题意:

求凸包周长。

总结:

测试模板。

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define N 100005
#define eps 1e-8 using namespace std; struct point
{
double x, y;
point(){}
point(double a, double b):x(a), y(b){}
point operator-(point a){//向量减法
return point(x-a.x, y-a.y);
}
point operator+(point a){//向量加法
return point(x+a.x, y+a.y);
}
double operator*(point a){//向量叉积
return x*a.y-y*a.x;
}
bool operator<(const point a)const{
if(fabs(x-a.x)<eps)return y<a.y;//浮点数的判等不能直接用‘==’直接比较
return x<a.x;
}
bool operator==(const point a)const{
return (fabs(x-a.x)==eps && fabs(y-a.y));
}
double len(){//向量的模
return sqrt(x*x+y*y);
}
}p[N], s[N];//p为点,s为栈 double cp(point a, point b, point o)//向量oa,ob叉积
{
return (a-o)*(b-o);
} void Convex(point *p, int &n)//Graham扫描法,栈内为所有凸包点
{
sort(p, p+n);
int top, m;
s[0] = p[0]; s[1] = p[1]; top = 1;
for(int i = 2; i < n; i++)//从前往后扫
{
while(top>0 && cp(p[i], s[top], s[top-1])>=0)top--;
s[++top] = p[i];
}
m = top;
s[++top] = p[n-2];
for(int i = n-3; i >= 0; i--)//从后往前扫
{
while(top>m && cp(p[i], s[top], s[top-1])>=0)top--;
s[++top] = p[i];
}
n = top;
} int main()
{
int n;
while(scanf("%d", &n)!=EOF && n)
{
for(int i = 0; i < n; i++)
scanf("%lf%lf", &p[i].x, &p[i].y);
sort(p, p+n);
int cnt=unique(p, p+n) - p;
if(cnt == 1){
printf("0.00\n");continue;
}else if(cnt==2){
printf("%.2lf\n", (p[1]-p[0]).len());continue;
}
Convex(p, cnt);
double ans = 0;
s[cnt] = s[0];
for(int i = 0; i < cnt; i++)ans+=(s[i+1]-s[i]).len();
printf("%.2lf\n", ans);
}
return 0;
}

最新文章

  1. java list 简述
  2. 【USACO 1.5】Prime Palindromes
  3. 使用基于关系的选择器和伪类选择器创建纯CSS无JavaScript的鼠标移动到上面即可显示的下拉菜单
  4. 在Oracle Linux Server release 6.4下配置ocfs2文件系统
  5. FreeBSD10上编译尝试DeepIn UI
  6. BZOJ2675 : Bomb
  7. 《A Tour of PostgreSQL Internals》学习笔记——系统表和数据类型
  8. SQL server数据类型int、bigint、smallint、tinyint
  9. JAVA 跑马灯文字效果
  10. overflow使用說明
  11. Raptor井字棋游戏
  12. 为什么String被设计为不可变?是否真的不可变?
  13. python安装提示No module named setuptools,wget提示ERROR 403: SSL is required
  14. GreenDao3.2的简单使用
  15. spring boot 配置注入
  16. 8、判断三角形ABC中是否有点D
  17. JavaScript -- Anchor
  18. [Selenium]如何实现上传本地文件
  19. A - Subsequence (算法 二分 )
  20. go语言之进阶篇同名字段

热门文章

  1. maven-shade-plugin插件未生效原因分析
  2. CSS 常见样式 特殊用法 贯穿线&amp;徽章&amp;箭头
  3. 3.Strom-并发机制
  4. domReady的理解
  5. Java源码赏析(六)Java String 三顾
  6. Android 自定义Vie 对勾CheckBox
  7. 开源两个spring api项目
  8. Power Designer建模之餐饮在线点评系统——业务处理模型
  9. makefile从入门到入门
  10. GetDlgItem(函数详解)