UVa 10088 - Trees on My Island （pick定理）

  1 #include"stdio.h"
  2 #include"string.h"
  3 #include"algorithm"
  4 #include"stdlib.h"
  5 #include"math.h"
  6 #include"map"
  7 #include"queue"
  8 #include"iostream"
  9 #define M 1009
 10 #define inf 0x3f3f3f3f
 11 #define eps 1e-9
 12 using namespace std;
 13 struct node
 14 {
 15     double x,y;
 16     node(){}
 17     node(double x,double y)
 18     {
 19         this->x=x;
 20         this->y=y;
 21     }
 22     node operator-(node a)
 23     {
 24         return node(x-a.x,y-a.y);
 25     }
 26     node operator+(node a)
 27     {
 28         return node(x+a.x,y+a.y);
 29     }
 30     double operator*(node a)
 31     {
 32         return x*a.x+y*a.y;
 33     }
 34     double operator^(node a)
 35     {
 36         return x*a.y-y*a.x;
 37     }
 38 }p[M];
 39 double len(node a)
 40 {
 41     return sqrt(a*a);
 42 }
 43 double dis(node a,node b)
 44 {
 45     return len(b-a);
 46 }
 47 double cross(node a,node b,node c)
 48 {
 49     return (b-a)^(c-a);
 50 }
 51 int gcd(int a,int b)
 52 {
 53     return b==0?a:gcd(b,a%b);
 54 }
 55 int point(node a,node b)
 56 {
 57     int m=(int)(fabs(b.x-a.x)+0.5);
 58     int n=(int)(fabs(b.y-a.y)+0.5);
 59     int r=gcd(m,n);
 60     return r-1;
 61 }
 62 int main()
 63 {
 64     int n;
 65     while(scanf("%d",&n),n)
 66     {
 67         for(int i=0;i<n;i++)
 68             scanf("%lf%lf",&p[i].x,&p[i].y);
 69         double sum=0;
 70         node O(0,0);
 71         double num=n;
 72         for(int i=0;i<n;i++)
 73         {
 74             num+=point(p[i],p[(i+1)%n]);
 75             sum+=cross(O,p[i],p[(i+1)%n]);
 76         }
 77         sum=fabs(sum)/2.0;
 78         double ans=sum+1-0.5*num;
 79         printf("%.0f\n",ans+0.001);
 80     }
 81     return 0;
 82 }
 83 /*
 84 12
 85 3 1
 86 6 3
 87 9 2
 88 8 4
 89 9 6
 90 9 9
 91 8 9
 92 6 5
 93 5 8
 94 4 4
 95 3 5
 96 1 3
 97 12
 98 1000 1000
 99 2000 1000
100 4000 2000
101 6000 1000
102 8000 3000
103 8000 8000
104 7000 8000
105 5000 4000
106 4000 5000
107 3000 4000
108 3000 5000
109 1000 3000
110 4
111 0 0
112 1000000 0
113 1000000 1000000
114 0 1000000
115 4
116 0 0
117 100 0
118 100 100
119 0 100
120 */