poj 1265 Area (pick定理+叉积求多边形面积）

题目：http://poj.org/problem?id=1265

pick定理：多边形S面积 = 多边形内部点数 + 边上的点数/2 -1；面积和边上的点数都为实数

边界格点数---利用斜边对应的直角边的最大公约数
多边形面积---利用叉积
 内部点数---利用pick定理求



代码：

View Code

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 using namespace std;
 5 int gcd (int a,int b)
 6 {
 7     if(b==0)
 8     return a;
 9     return gcd(b,a%b);
10 }
11 int area(int x1,int y1,int x2,int y2)
12 {
13     return x1*y2-x2*y1;
14 }
15 int main()
16 {
17     int t,n,i;
18     int x,y;
19     int k=0;
20     scanf("%d",&t);
21     while(t--)
22     {
23         scanf("%d",&n);
24         k++;
25         int edge=0;
26         int in=0;
27         int x1=0;
28         int y1=0;
29         int S=0;
30         int x2,y2;
31         for(i=0;i<n;i++)
32         {
33             scanf("%d%d",&x,&y);
34             edge+=gcd(fabs(x),fabs(y));//边界格点数
35             //cout<<gcd(fabs(x),fabs(y))<<endl;
36             x2=x1+x;
37             y2=y1+y;
38             S+=area(x1,y1,x2,y2);//叉积求面积
39             x1=x2;
40             y1=y2;
41         }
42         in=S/2-edge/2+1;
43         printf("Scenario #%d:\n%d %d %.1f\n\n",k,in,edge,S/2.0);
44     }
45     return 0;
46 }