在discuss的提示下比较轻松的切了这道题，了解了pick定理......
要点： （1） pick定理：
给定顶点座标均是整点（或
正方形格点）的简单
多边形，
皮克定理说明了其
面积A和内部格点数目
i、边上格点数目
b的关系：
A =
i +
b/2 - 1；
定理转载链接：
Pick定理 （2） 在两点（x1，y1），（x2，y2）连线之间的整点个数（包含一个端点）为：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 阅读(554)
评论(0) 编辑 收藏 引用