zoj1032解题报告
2024-07-30 03:47:00 221人阅读
一道几何题,开始不知道pick定理,于是就暴力..在一定范围内判断该点是否在多边形内,大致做法就是用该点作一条平行于x的射线,看与多边形的交点个数,其中注意的是若交点恰好为多边形的顶点要忽略.判断点是否在线段上,和求多边形面积可以用模板,结果超时..后来搜了下发现了pick定理,瞬间简单了很多. Pick定理:设以整数点为顶点的多边形的面积为S, 多边形内部的整数点数为N, 多边形边界上的整数点数为L, 则 N + L/2 - 1 = S. 果然像几何题,数论题不知道公式不行啊,只能多做这样题慢慢积累了. 代码如下: #include #include
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉:
投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。