【題解】CSES 2193 Polygon Lattice Points

【題目敘述】https://cses.fi/problemset/task/2193/

#include <iostream>
using namespace std;
 
int n;
 
struct Point{
    long long x, y;
    Point operator+(Point b){
        return {x+b.x, y+b.y};
    }
    Point operator-(Point b){
        return {x-b.x, y-b.y};
    }
}a[100005];
 
long long cross(Point a, Point b){
    return a.x*b.y - a.y*b.x;
}
 
long long area(Point a[], int sz){
    long long ret = 0;
    for (int i = 1; i < sz; i++){
        ret += cross(a[i-1], a[i]);
    }
    ret += cross(a[n-1], a[0]);
    return abs(ret);
}
 
long long gcd(long long x, long long y){
    if (y == 0) return x;
    return gcd(y, x%y);
}
 
int main() {
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> a[i].x >> a[i].y;
    }
    long long cnt = 0;
    for (int i = 1; i < n; i++){
        cnt += gcd(abs(a[i].x-a[i-1].x), abs(a[i].y-a[i-1].y));
    }
    cnt += gcd(abs(a[n-1].x-a[0].x), abs(a[n-1].y-a[0].y));
    cout << (area(a, n)-cnt+2)/2 << " " << cnt << "\n";
}
分享本文 Share with friends