Mr.一首歌
能不能给我一首歌的时间,我只有三分钟的热度
posts - 4,comments - 0,trackbacks - 0
【背景】话说Mr.一首歌根本不会计算几何此等神物啊,但是当小学妹问起自己凸包神马的东西时,自己幸好还收藏着一个模版,于是就给了人家模版看,叫人家看懂graham思想后再来交流,这才发现要开始好好学计算几何了(此等动机不纯,小朋友们千万不要学我这个坏榜样)。
1.基础
❤多边形重心的计算
求多边形重心的题目大致有这么几种:
1、质量集中在顶点上
n个顶点坐标为(xi,yi),质量为mi,则重心
  X = ∑( xi×mi ) / ∑mi
  Y = ∑( yi×mi ) / ∑mi
  特殊地,若每个点的质量相同,则
  X = ∑xi / n
  Y = ∑yi / n
2、质量分布均匀
  特殊地,质量均匀的三角形重心:
  X = ( x0 + x1 + x2 ) / 3
  Y = ( y0 + y1 + y2 ) / 3
3、质量分布不均匀
只能用函数多重积分来算,不太会
这题的做法:
将n边形分成多个三角形,分别求出重心坐标以及质量m【因为质量分布均匀,所以可以设密度为1,则面积就是质量】
因为质量都集中在重心
所以把所有求出来的重心按逆时针连接起来又是一个多边形
但是这个多边形的质量集中在顶点上
所以可以利用上面公式进行计算
例:hdu1115
hdu1115

❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤
2.凸包
㈠graham扫描法的一些应用
graham模版

hdu1392 求凸包周长
求得凸包后,求出相邻点的距离总和即可

hdu2202 求最大三角形:找到了凸包的点,同过叉积求三角形的面,最终找出最大的就OK了

hdu3285 
题目要把凸包边上的点输出,输出有两个规则,
1.按照y的值最大的先输出,如果一值相等就按照X值小的先输出。
2.之后要按照顺时针输出点的位置。当时自己在做的时候,用的凸包模板,凸包上的点是按逆时针保存,而却没有1条那样的规则,后来到,把逆时针倒过来就是顺时针,在去找到那个满足第一个条件的那个点在数组中位置,再从找到的位置输出就行了

poj1113 
求出凸包的周长再加上一L为半径的圆的周长就是要求的

今天就到这里了,谢谢各位关心:)  22:53 2012/9/8 by Mr.一首歌

posted on 2012-09-08 22:20 Mr.OneSong 阅读(157) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理