在discuss的提示下比較輕松的切了這道題，了解了pick定理......
要點(diǎn)： （1） pick定理：
給定頂點(diǎn)座標(biāo)均是整點(diǎn)（或
正方形格點(diǎn)）的簡(jiǎn)單
多邊形，
皮克定理說(shuō)明了其
面積A和內(nèi)部格點(diǎn)數(shù)目
i、邊上格點(diǎn)數(shù)目
b的關(guān)系：
A =
i +
b/2 - 1；
定理轉(zhuǎn)載鏈接：
Pick定理 （2） 在兩點(diǎn)（x1，y1），（x2，y2）連線(xiàn)之間的整點(diǎn)個(gè)數(shù)（包含一個(gè)端點(diǎn)）為：gcd（|x1－x2|，|y1－y2|）；
（3） 求三角形面積用叉乘
2007.10.26
Simbaforrest
1 #include<stdio.h>
2 #include<math.h>
3 typedef struct tagPoint
4 {
5 int x,y;
6 }Point;
7
8 int double_area(Point a,Point b,Point c)
9 {
10 return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
11 }
12
13 int gcd(int a,int b)
14 {
15 if(b==0)
16 return a;
17 return gcd(b,a%b);
18 }
19
20 int edgenum(Point a,Point b)
21 {
22 int dx,dy;
23 dx=a.x-b.x;
24 if(dx<0)
25 dx=-dx;
26 dy=a.y-b.y;
27 if(dy<0)
28 dy=-dy;
29 return gcd(dx,dy);
30 }
31
32 int main()
33 {
34 int ab,bc,ca;
35 int edge,area,in;
36 Point a,b,c;
37 while(scanf("%d%d%d%d%d%d",&a.x,&a.y,&b.x,&b.y,&c.x,&c.y),a.x||a.y||b.x||b.y||c.x||c.y)
38 {
39 area=double_area(a,b,c);
40 if(area<0)
41 area=-area;
42 ab=edgenum(a,b);
43 bc=edgenum(b,c);
44 ca=edgenum(c,a);
45 edge=ab+bc+ca;
46 in=(area-edge+2)/2;
47 printf("%d\n",in);
48 }
49 return 0;
50 }
51
posted on 2007-10-26 17:45
R2 閱讀(563)
評(píng)論(0) 編輯 收藏 引用