Pick 定理?? 設(shè)以整數(shù)點(diǎn)為頂點(diǎn)的多邊形的面積為S，多邊形內(nèi)部的整數(shù)點(diǎn)數(shù)為N，多邊形邊界上的整數(shù)點(diǎn)數(shù)為L(zhǎng),則

??????????????? N+1/2L-1=S.

????? 對(duì)于N與L的計(jì)算由下面的程序給出：

typedef struct Point

{

????? int x,y;

}POINT;

int gcd(int a,int b)???????????????????????? //求數(shù)a,b的最大公因數(shù)

{

???? if(b==0) return a;

???? else return gcd(b,a%b);

}

多邊形邊上的網(wǎng)格點(diǎn)個(gè)數(shù)有下列程序段給出：

int OnEdge(int n,POINT *p)

{

???? int i,ret=0;

???? for(i=0;i<n;i++)

????????? ret+=gcd(fabs(p[i].x-p[(i+1)%n].x),fabs(p[i].y-p[(i+1)%n].y));

???? return ret;

}

多邊形內(nèi)部的網(wǎng)格點(diǎn)個(gè)數(shù)由下列程序段給出：

int InSide(int n,POINT *p)

{

??? int i,area=0;

??? for(i=0;i<n;i++) area+=p[(i+1)%n].y*(p[i].x-p[(i+2)%n].x);???????????//計(jì)算面積

????return (fabs(area)-OnEdge(n,p))/2?+1;

}

?

問題描述

????? 格點(diǎn)是一個(gè)有序(x,y)，其中x和y都是整數(shù)。給定三角形的頂點(diǎn)坐標(biāo)（碰巧是格點(diǎn)）,要你計(jì)算完全在三角形中的頂點(diǎn)個(gè)數(shù)（三角形邊上和三角形的頂點(diǎn)不必計(jì)算)。

輸入????

???? 輸入有多組測(cè)試數(shù)據(jù)。每組測(cè)試數(shù)據(jù)由6個(gè)整數(shù)x1,y1,x2,y2,x3和y3組成，其中，（x1,y1)、（x2,y2)和（x3,y3)是三角形的頂點(diǎn)坐標(biāo)。輸入中的所有三角形都是非退化的（有正的面積）,-15000≤x1,y1,x2,y2,x3,y3≤15000。當(dāng)輸入的數(shù)滿足x1=y1=x2=y2=x3=y3=0時(shí)表示輸入結(jié)束，不必處理。

輸出

???? 對(duì)每組測(cè)試數(shù)據(jù)，單行上輸出三角形內(nèi)部格點(diǎn)的個(gè)數(shù)。

輸入樣例????????????????????????????????????????????????? 輸出樣例

0 0 1 0 0 1????????????????????????????????????????????? 0

0 0 5 0 0 5????????????????????????????????????????????? 6

0 0 0 0 0 0????

?

分析

???? 本題可直接用Pick定理：area=OnEdge/2+InSide-1，其中area為頂點(diǎn)都是格點(diǎn)的多邊形的面積，OnEdge為多邊形上的格點(diǎn)數(shù)，InSide為多邊形內(nèi)部的格點(diǎn)數(shù)。

???? 多邊形的面積可用叉積計(jì)算，但注意可能為負(fù)值，需轉(zhuǎn)換。給定兩個(gè)格點(diǎn)A（x0,y0），B（x1,y1)。設(shè)C(X,Y)是線段AB上的一個(gè)結(jié)點(diǎn)。那么，x=x0+λ(x1-x0)，y=y0+λ(y1-y0)，（0≤λ≤1)。要使x與y均為整數(shù)，λ必為一個(gè)分?jǐn)?shù)，而且λ的分母是x1-x0與y1-y0的公因數(shù)，因此可用最大公因數(shù)算法gcd求得。

?

參考程序

?

#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
typedef struct Point
{
int x,y;
}POINT;
int gcd(int a,int b)
{
if(b==0) return a;
else return gcd(b,a%b);
}
int Int_area(POINT a,POINT b,POINT c) //平行四邊形面積
{
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
int edgenum(POINT a,POINT b)
{
int dx,dy;
dx=a.x-b.x;
if(dx<0) dx=-dx;
dy=a.y-b.y;
if(dy<0) dy=-dy;
return gcd(dx,dy);
}
int main()
{
POINT a,b,c;
int area,OnEdge,InSide;
while(cin>>a.x>>a.y>>b.x>>b.y>>c.x>>c.y&&(a.x||a.y||b.x||b.y||c.x||c.y))
{
area=Int_area(a,b,c);
if(area<0) area=-area;
OnEdge=edgenum(a,b)+edgenum(b,c)+edgenum(c,a);
InSide=(area-OnEdge+2)/2; //Pick定理應(yīng)用，area是三角形面積的2倍
cout<<InSide<<endl;
}
return 0;
}

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/zzw818/archive/2011/11/02/2232720.html

總結(jié)

以上是生活随笔為你收集整理的整数点与Pick定理的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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