皮克定理為我們解答了關(guān)于多邊形面積和格點(diǎn)數(shù)的一些內(nèi)在關(guān)系，具體如下：

（前提是頂點(diǎn)坐標(biāo)都是整數(shù)點(diǎn)或是正方形格點(diǎn)的簡單多邊形）我們假設(shè)簡單多邊形A的面積是S，A內(nèi)部的格點(diǎn)數(shù)為kin,A邊上格點(diǎn)數(shù)數(shù)目為kon，則它們之間存在如下關(guān)系：S=kin+kon/2-1。

wikipedia上的詳細(xì)證明

PKU 2954就是皮克定理的簡單應(yīng)用。

代碼如下：

#include"stdio.h" #include"math.h" #define abs(x) ((x)>0?(x):-(x)) struct point{int x,y;}; int gcd(int a,int b) {return b?gcd(b,a%b):a; } int on(point *p)//計(jì)算邊上的格點(diǎn)數(shù) {int i,ret=0;for(i=0;i<3;i++)ret+=gcd(abs(p[i].x-p[(i+1)%3].x),abs(p[i].y-p[(i+1)%3].y));return ret; } int in(point *p)//計(jì)算內(nèi)部的格點(diǎn)數(shù) {int i,ret=0;for(i=0;i<3;i++)ret+=p[(i+1)%3].y*(p[i].x-p[(i+2)%3].x);return (abs(ret)-on(p))/2+1; } int main() {point p[3];while(scanf("%d%d%d%d%d%d",&p[0].x,&p[0].y,&p[1].x,&p[1].y,&p[2].x,&p[2].y)){if(p[0].x==0&&p[0].y==0&&p[1].x==0&&p[1].y==0&&p[2].x==0&&p[2].y==0)break;int ans=in(p);printf("%d\n",ans);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/acsmile/archive/2011/04/30/2033549.html

總結(jié)

以上是生活随笔為你收集整理的pick定理的应用的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。