Q:皮克定理這種一句話的東西為什么還要寫學(xué)習(xí)筆記啊？

A:多好玩啊...

PS:除了藍(lán)色字體之外都是廢話啊...

---

?Part I

1.頂點(diǎn)全在格點(diǎn)上的多邊形叫做格點(diǎn)多邊形(坐標(biāo)全是整數(shù))

2.維基百科

Given a?simple polygon?constructed on a grid of equal-distanced points (i.e., points with?integer?coordinates) such that all the polygon's vertices are grid points,?Pick's theorem?provides a simple?formula?for calculating the?area?A?of this polygon in terms of the number?i?of?lattice points in the interior?located in the polygon and the number?b?of?lattice points on the boundary?placed on the polygon's perimeter:^[1]

?

3.看不懂英文？

S=a+b/2-1，其中a表示多邊形內(nèi)部的點(diǎn)數(shù)，b表示多邊形邊界上的點(diǎn)數(shù)，s表示多邊形的面積。

證明：

1.先證明直角三角形和矩形 在逆用證明任意三角形，歸納法證明任意多邊形

2.

From:http://www.matrix67.com/blog/archives/768

最酷的證明：Pick定理另類證法

????難以想像，一段小小的證明竟然能比一個(gè)瘦小的留著長(zhǎng)頭發(fā)穿黑色短袖T恤緊身牛仔褲邊跳邊彈吉他的MM還要酷。原來(lái)一直以為這個(gè)證明已經(jīng)很酷了，現(xiàn)在顯然我已經(jīng)找到了一個(gè)更酷的證明。
????Pick定理是說，假設(shè)平面上有一個(gè)頂點(diǎn)全在格點(diǎn)上的多邊形P，那么其面積S(P)應(yīng)該等于i+b/2-1，其中i為多邊形內(nèi)部所含的格點(diǎn)數(shù)，b是多邊形邊界上的格點(diǎn)數(shù)。絕大多數(shù)證明都是用割補(bǔ)的辦法重新拼拆多邊形。這里，我們來(lái)看一個(gè)另類的證明。
????假設(shè)整個(gè)平面是一個(gè)無(wú)窮大的鐵板；在0時(shí)間，每個(gè)格點(diǎn)上都有一個(gè)單位的熱量。經(jīng)過無(wú)窮長(zhǎng)時(shí)間的傳導(dǎo)后，最終這些熱量將以單位密度均勻地分布在整個(gè)鐵板上。下面我們?cè)囍蠖噙呅蜳內(nèi)的熱量?？紤]多邊形的每一條線段e：它的兩個(gè)端點(diǎn)均在格點(diǎn)上，因此線段e的中點(diǎn)是整個(gè)平面格點(diǎn)的對(duì)稱中心，因而流經(jīng)該線段的熱量收支平衡（這半邊進(jìn)來(lái)了多少那半邊就出去了多少），即出入該線段的熱量總和實(shí)際為0。我們立即看到，P的熱量其實(shí)完全來(lái)自于它自身內(nèi)部的i個(gè)格點(diǎn)（的全部熱量），以及邊界上的b個(gè)格點(diǎn)（各自在某一角度范圍內(nèi)傳出的熱量）。邊界上的b個(gè)點(diǎn)形成了一個(gè)內(nèi)角和為(b-2)*180的b邊形，從這b個(gè)點(diǎn)流入P的熱量為(b-2)*180/360 = (b-2)/2 = b/2-1。在再加上i個(gè)內(nèi)部格點(diǎn)，于是S(P)=i+b/2-1。

Part II

一條端點(diǎn)在格點(diǎn)上的線段覆蓋的點(diǎn)數(shù)：

gcd(dx,dy)?dxdy分別為線段橫向占的點(diǎn)數(shù)和縱向占的點(diǎn)數(shù)

證明：自己隨便想想就知道了，和這道題的思想有點(diǎn)像：http://www.cnblogs.com/candy99/p/6074673.html

?

---

?

?

于是就可以做裸題了....

POJ 2954 三角形內(nèi)部格點(diǎn)數(shù)

?

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <vector> using namespace std; typedef long long ll; const int N=105; const double eps=1e-8; inline int read(){char c=getchar();int x=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}return x*f; } inline int sgn(double x){if(abs(x)<eps) return 0;else return x<0?-1:1; } struct Vector{int x,y;Vector(int a=0,int b=0):x(a),y(b){} }; typedef Vector Point; Vector operator +(Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);} int Cross(Vector a,Vector b){return a.x*b.y-a.y*b.x; }int n,x,y,x2,y2,x3,y3,b,s; int gcd(int a,int b){return b==0?a:gcd(b,a%b);} int main(int argc, const char * argv[]){while(scanf("%d",&x)!=EOF){y=read();x2=read();y2=read();x3=read();y3=read();if(!x&&!y&&!x2&&!y2&&!x3&&!y3) break;b=s=0;b=gcd(abs(x2-x),abs(y2-y))+gcd(abs(x3-x2),abs(y3-y2))+gcd(abs(x3-x),abs(y3-y));s=abs(Cross(Vector(x2-x,y2-y),Vector(x3-x,y3-y)));printf("%d\n",(s-b+2)/2);}return 0; }

?

POJ1265?給一個(gè)平面上的簡(jiǎn)單多邊形，求邊上的點(diǎn)，多邊形內(nèi)的點(diǎn)，多邊形面積。

?

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <vector> using namespace std; typedef long long ll; const int N=105; const double eps=1e-8; inline int read(){char c=getchar();int x=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}return x*f; } inline int sgn(double x){if(abs(x)<eps) return 0;else return x<0?-1:1; } struct Vector{int x,y;Vector(int a=0,int b=0):x(a),y(b){} }; typedef Vector Point; Vector operator +(Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);} int Cross(Vector a,Vector b){return a.x*b.y-a.y*b.x; }int n,x,y,b,s; Point poly[N]; int gcd(int a,int b){return b==0?a:gcd(b,a%b);} int main(int argc, const char * argv[]){int T=read(),cas=0;while(T--){b=s=0;n=read();for(int i=1;i<=n;i++){x=read();y=read();b+=gcd(abs(x),abs(y));poly[i]=poly[i-1]+Point(x,y);s+=Cross(poly[i],poly[i-1]);}s=abs(s);printf("Scenario #%d:\n",++cas);printf("%d %d %.1f\n\n",(s+2-b)/2,b,0.5*s);}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/candy99/p/pick.html

總結(jié)

以上是生活随笔為你收集整理的poj12652954 [皮克定理 格点多边形]【学习笔记】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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