【计算几何】Water Testing

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn = 2e6+50;
 5  
 6 ll gcd(ll u,ll v){
 7     return (v == 0ll) ? u : gcd(v,u%v);
 8 }
 9  
10 typedef struct point{
11     ll x , y ;
12     point() {}
13     point(ll a,ll b):x(a),y(b) {}
14     void input(){
15         scanf("%lld%lld",&x,&y);
16     }
17     friend point operator + ( const point &a , const point &b ){
18         return point(a.x + b.x , a.y + b.y );
19     }
20     friend point operator - ( const point &a , const point &b ){
21         return point(a.x - b.x , a.y - b.y );
22     }
23  
24 }point;
25  
26  
27  
28 point List[maxn];
29 ll det(const point & a , const point & b){
30     return a.x * b.y - a.y * b.x ;
31 }
32  
33  
34 ll Abs( ll x ){
35     return (x>=0?x:-x);
36 }
37  
38  
39 ll area( point a[] ,int n)
40 {
41     ll sum = 0 ;
42     a[n] = a[0] ;
43     for(int i=0; i<n; i++) sum += det(a[i+1],a[i]);
44     return sum ;
45 }
46 ll Border_Int_Point_Num( point a[] , int n)
47 {
48     ll num = 0 ;
49     a[n] = a[0];
50     for(int i=0; i<n; i++)
51     {
52         if( Abs((a[i+1].x-a[i].x)) == 0  ){
53             num += Abs(a[i+1].y-a[i].y);
54         }else if( Abs((a[i+1].y-a[i].y)) == 0 ){
55             num += Abs(a[i+1].x-a[i].x);
56         }else{
57             num += gcd(Abs(ll(a[i+1].x-a[i].x)),Abs(ll(a[i+1].y-a[i].y)));
58         }
59     }
60     return num ;
61 }
62 ll Inside_Int_Point_Num( point a[] , int n )
63 {
64     ll Area = area(a,n) ;
65     Area = Abs(Area);
66     return ( Area - Border_Int_Point_Num(a,n) ) / 2 + 1 ;
67  
68 }
69 //polyon S ;
70  
71 int n;
72 int main()
73 {
74     scanf("%d",&n);
75     //S.n = n ;
76  
77     for(int i=0;i<n;i++)
78         List[i].input();
79     /*
80     sort ( List , List + n , cmp );
81  
82     for(int i=n-1;i>=0;i--){
83         S.a[i] = List[n-i-1] ;
84     }
85  
86     for(int i=0;i<n;i++){
87         scanf("%lld%lld",&S.a[i].x,&S.a[i].y);
88     }
89     */
90     printf("%lld\n",Inside_Int_Point_Num(List,n));
91     return 0;
92 }