计算几何PPTPPT课件.pptx

该【计算几何PPTPPT课件 】是由【非学无以广才】上传分享，文档一共【84】页，该文档可以免费在线阅读，需要了解更多关于【计算几何PPTPPT课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。计算几何
钟思思
/
1
1/84
目录
序言
准备知识
向量
多边形
Voronoi介绍
例题讲解
2
2/84
序言
3
3/84
序言
计算几何是计算机理论科学一个主要分支。
自20世纪70年代末从算法设计与分析中独立出来起,不到30年,该学科已经有了巨大发展,不但产生了一系列主要理论结果,也在众多实际领域中得到了广泛应用。
常见应用领域:计算机图形学,机器人学,地理信息系统(GIS),CAD/CAM………..
4
4/84
序言
在ICPC竞赛中,计算几何相比于其它部分来说是比较独立。
除近年来出现与图论和动态规划相结合题目,计算几何与其它知识点极少有过多结合。
计算几何题目难度不会很大,但也永远不会成为最弱题。
计算几何题目含有代码量大、特殊情况多、精度问题难以控制等特点。
5
5/84
准备知识
6
6/84
准备知识
头文件#include<cmath>
浮点数double
常量
constdoublePI=acos(-);
#
constdoubleINF=1e100;
constdoubleEPS=1e-6;
7
7/84
准备知识
符号函数
intsign(doubled)
{
if(fabs(d)<EPS)return0;
return(d>0)?1:-1;
}
8
8/84
准备知识
浮点数转化成整数
地板函数floor(x)
天花板函数ceil(x)
四舍五入(int)(x+)
下取整(int)(x+ERROR)
尽可能少用三角函数、除法、开方、求幂、取对数
9
9/84
浮点误差
请不要直接用等号判断浮点数是否相等!
处理方法一,误差判断法:
constdoubleEPS=1e-9;
浮点数判断相等,fabs(x-y)<EPS;
浮点数判断为零,fabs(x)<EPS。
处理方法二,化浮为整法:
在不溢出整数范围情况下,能够经过乘上10k次方,转化为整数运算,最终在将结果转化为整数。
10
10/84