POJ1265：皮克定理的应用与解析

1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7
8 #define N 222
9
10 using namespace std;
11 //[Pick定理] 设以整数点为顶点的多边形的面积为S&＃xff0c; 多边形内部的整数点数为N, 多边形边界上的整数点数为L&＃xff0c; 则 N &＃43; L/2 - 1 &＃61; S
12 struct PO
13 {
14 int x,y;
15 }p[N];
16
17 int n,gs;
18
19 inline void read()
20 {
21 scanf("%d",&n);
22 for(int i&＃61;1,a&＃61;0,b&＃61;0,c,d;i<&＃61;n;i&＃43;&＃43;)
23 {
24 scanf("%d%d",&c,&d);
25 a&＃43;&＃61;c; b&＃43;&＃61;d;
26 p[i].x&＃61;a; p[i].y&＃61;b;
27 }
28 }
29
30 inline int cross(PO &a,PO &b,PO &c)
31 {
32 return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
33 }
34
35 inline int gcd(int a,int b)
36 {
37 int ys;
38 while(b)
39 {
40 ys&＃61;a%b;
41 a&＃61;b; b&＃61;ys;
42 }
43 return a;
44 }
45
46 inline int getnum(PO &a,PO &b)
47 {
48 int x&＃61;abs(a.x-b.x),y&＃61;abs(a.y-b.y);
49 return gcd(x,y)-1;
50 }
51
52 inline int getarea()
53 {
54 int ans&＃61;0;
55 for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) ans&＃43;&＃61;cross(p[0],p[i],p[i&＃43;1]);
56 return ans;
57 }
58
59 inline void go()
60 {
61 p[n&＃43;1]&＃61;p[1];
62 int edgenum&＃61;n;
63 for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) edgenum&＃43;&＃61;getnum(p[i],p[i&＃43;1]);
64 int area&＃61;abs(getarea());
65 int innum&＃61;(area-edgenum)/2&＃43;1;
66 printf("Scenario #%d:\n",&＃43;&＃43;gs);
67 printf("%d %d %.1lf\n\n",innum,edgenum,area*0.5);
68 }
69
70 int main()
71 {
72 int cas; scanf("%d",&cas);
73 while(cas--) read(),go();
74 return 0;
75 }