Pick's Theorem

今天做到某题(POJ 2954),题意是求一个顶点坐标均为整数的三角型内整数点的个数,不含三角型边上的整数点。

Pick's Theorem,大意是:任何平面上顶点坐标均为整数的简单多边形,满足以下公式:

A = I + B / 2 - 1

A是多边形的面积,I是多边形内的整数点的个数,B是多边形边上整数点的个数。

Pick's Theorem可以推广到多维的情况,见:Ehrhart polynomials

理论和题目配合得相当完美……汗啊……


发表评论

电子邮件地址不会被公开。 必填项已用*标注