codevs1298, hdu1392 (凸包模板)
2024-08-28 09:33:44
题意:
求凸包周长。
总结:
测试模板。
代码:
#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;
}
最新文章
- java list 简述
- 【USACO 1.5】Prime Palindromes
- 使用基于关系的选择器和伪类选择器创建纯CSS无JavaScript的鼠标移动到上面即可显示的下拉菜单
- 在Oracle Linux Server release 6.4下配置ocfs2文件系统
- FreeBSD10上编译尝试DeepIn UI
- BZOJ2675 : Bomb
- 《A Tour of PostgreSQL Internals》学习笔记——系统表和数据类型
- SQL server数据类型int、bigint、smallint、tinyint
- JAVA 跑马灯文字效果
- overflow使用說明
- Raptor井字棋游戏
- 为什么String被设计为不可变?是否真的不可变?
- python安装提示No module named setuptools,wget提示ERROR 403: SSL is required
- GreenDao3.2的简单使用
- spring boot 配置注入
- 8、判断三角形ABC中是否有点D
- JavaScript -- Anchor
- [Selenium]如何实现上传本地文件
- A - Subsequence (算法 二分 )
- go语言之进阶篇同名字段