Area POJ

Area

题意：起始点原点，给你线段横向占x点，纵向占y点，求该过程走完图形的面积，在线上格点上的点数和在图形内部的点数

思路：1.皮克定理，s=in+on/2+1，可以利用多边形面积公示先求出面积，

　　　2.线上的点数为gcd(x,y)

　　　3.再利用皮克定理求出内部的点数

 1 // 
 2 // Created by HJYL on 2020/2/4.
 3 //
 4 #include<iostream>
 5 #include<cstring>
 6 #include<cstdio>
 7 #include<cstring>
 8 #include<math.h>
 9 #include<algorithm>
10 using namespace std;
11 const double eps=1e-8;
12 const int maxn=1e6+5;
13 long long gcd(long long a,long long b) {
14     while (b) {
15         int r = b;
16         b = a % b;
17         a = r;
18     }
19     return a;
20 }
21 struct Point{
22     int x,y;
23     Point(int x=0,int y=0):x(x),y(y){}
24     Point operator - (Point const &b)const
25     {
26         return Point(x-b.x ,y-b.y);
27     }
28     bool operator < (Point const &c)const{
29         if(x==c.x)
30             return y<c.y;
31         return x<c.x;
32     }
33 }p[maxn];
34 double Cross(Point A,Point B)
35 {
36     return (A.x*B.y)-(A.y*B.x);
37 }
38 long long PolygonArea(Point* p, int n) {//p为端点集合，n为端点个数
39     long long s = 0;
40     for (int i = 1; i < n - 1; ++i)
41         s += Cross(p[i] - p[0], p[i + 1] - p[0]);
42     return s<0?-s:s;
43 }
44 int main()
45 {
46     int T;
47     scanf("%d",&T);
48     int Case=1;
49     while(T--)
50     {
51         int n;
52         scanf("%d",&n);
53         p[0].x=0,p[0].y=0;
54         int x,y;
55         long long on=0;
56         for(int i=1;i<=n;i++)
57         {
58             scanf("%d%d",&x,&y);
59             p[i].x=p[i-1].x+x;
60             p[i].y=p[i-1].y+y;
61             on+=gcd(abs(x),abs(y));
62         }
63         long long s=PolygonArea(p,n+1);//s=on/2+in-1;
64         long long in=(s+2-on)/2;
65         printf("Scenario #%d:
",Case++);
66         printf("%lld %lld %.1lf

",in,on,s/2.0);
67 
68     }
69     return 0;
70 }