皮克定理

对于顶点坐标均为整点的简单多边形，其面积$S$、内部格点数$n$、多边形边界上的格点数$s$满足如下关系:

$ S=n+\frac{s}{2}-1$

例题 POJ 2954

已知三角形三个点坐标，求三角形内部整数点的个数

根据公式，只要求出三角形面积（可以通过叉乘得出）和三条边上整点个数$s$，即可得到内部整点个数

对于两点之间整数点的个数（不含两个端点），有如下公式：

设$dx=abs(x_1-x_0),dy=abs(y_1-y_0)$

若$dx=0$，则$s=dy-1$

若$dx\ne 0$，则$s=sizeof(\{val\mid 0\lt val\le dx, (val\mid\frac{dx}{gcd(dx,dy)})\})-1=gcd(dx,dy) - 1$

两种情况合并一下，得到答案$s=gcd(dx,dy)-1$

#include <iostream>
#include <algorithm>

using namespace std;

struct point{
    int x, y;
}points[3];

struct vec{
    int x, y;
    vec(point & from, point & to){x = to.x-from.x, y = to.y-from.y;}
    int operator *(const vec & p)const{return x*p.y - y*p.x;}
};

void solve(){
    int area = abs(vec(points[0], points[1]) * vec(points[0], points[2])) / 2;
    vec line[] = {vec(points[0], points[1]), vec(points[0], points[2]), vec(points[1], points[2])};
    int point_on_edge = 3;
    for(int i=0; i<3; i++){
        line[i].x = abs(line[i].x);
        line[i].y = abs(line[i].y);
        int gcd = __gcd(line[i].x, line[i].y);
        point_on_edge += gcd - 1;
    }
    int n = area + 1 - point_on_edge / 2;
    cout << n << '\n';
}

signed main(){
    while(cin >> points[0].x >> points[0].y >> points[1].x >> points[1].y >> points[2].x >> points[2].y){
        bool flag = true;
        for(int i=0; i<3; i++) if(points[i].x != 0 || points[i].y != 0) flag = false;
        if(flag) break;
        solve();
    }
}

例题 Codeforces 559D

#include <bits/stdc++.h>
#define ll long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)

using namespace std;

const int maxn = 1e5 + 100;
struct point{
    ll x, y;
    point(){}
    point(ll a, ll b): x(a), y(b){}
    point(point & from, point & to){x = to.x-from.x, y = to.y-from.y;}
    point operator -(const point & p)const{return point(x-p.x, y-p.y);}
    ll operator *(const point & p)const{return x*p.y - y*p.x;}
    int point_on_edge(){
        return __gcd(abs(x), abs(y));
    }
}points[maxn];

int n;

double area(int begin, int end){
    ll ans = 0;
    for(int i=begin; i!=end; i=(i+1)%n){
        ans += points[i] * points[(i+1)%n];
    }
    ans += points[end] * points[begin];
    return ans / 2.0;
}

long double pow2[120000];
long double prob(int len){
    if(n <= 60) return (pow2[n-len] - 1.0) / (pow2[n] - n - 1 - 0.5 * n * (n-1));
    return 1 / pow2[len];
}

long double pick(double area, double p){
    return area + 1 - p * 0.5;
}

void solve(){
    cin >> n;
    pow2[0] = 1;
    for(int i=1; i<=n; i++) pow2[i] = pow2[i-1] * 2;

    for(int i=0; i<n; i++) cin >> points[i].x >> points[i].y;
    long double point_on_edge = 0;
    long double total_area = area(0, n-1);
    for(int i=0; i<n; i++){
        point_on_edge += point(points[i], points[(i+1)%n]).point_on_edge();
    }
    long double estimate = 0;
    for(int i=0; i<n; i++){
        ll prev_area = points[i] * points[(i+1)%n] + points[(i+1)%n] * points[(i+2)%n];
        ll prev_poe = point(points[i], points[(i+1)%n]).point_on_edge() + point(points[(i+1)%n], points[(i+2)%n]).point_on_edge();
        for(int j=(i+2)%n, len=3; (j+1)%n != i && len < 60; j=(j+1)%n, len++){
            long double area = (prev_area + points[j] * points[i]) * 0.5;
            ll poe = point(points[j], points[i]).point_on_edge();
            estimate += (pick(area, prev_poe + poe) + poe - 1) * prob(len);
            prev_area += points[j] * points[(j+1)%n];
            prev_poe += point(points[j], points[(j+1)%n]).point_on_edge();
        }
    }
    cout << fixed << setprecision(11) << pick(total_area, point_on_edge) - estimate << endl;
}

signed main(){
    Android;
    solve();
}