首页 > 代码库 > USACO 3.4 Electric Fence 皮克定理
USACO 3.4 Electric Fence 皮克定理
题意:在方格纸上画出一个三角形,求三角形里面包含的格点的数目
因为其中一条边就是X轴,一开始想的是算出两条边对应的数学函数,然后枚举x坐标值求解。但其实不用那么麻烦。
皮克定理:给定顶点坐标均是整点(或正方形格点)的简单多边形,皮克定理说明了其面积A和内部格点数目i、边上格点数目b的关系:A = i + b/2 - 1。
有了这条定理就好办了。
三角形面积直接用公式就能算出来。
对于从点(0,0)到点(x,y)的线段,该线段上的格点数目即gcd(x,y)+1
这样A和b都有了,套公式就行了。
USACO 3.4 Electric Fence 皮克定理
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。