10088 – Trees on My Island

Given a polygon whose vertices are of integer coordinates (lattice points), count the number of lattice points within that polygon.
Pick’s theoreom states that
Where

• is the number of lattice points in the interior (this is our program’s output).
• is the area of the polygon.
• is the number of lattice points on the exterior.

All the reqired quantities are easily computable, however, needs some extra work. To find the number of lattice points on line segment , we simply calculate .
C++ implementation with rank 329:

#include <iostream>
#include <algorithm>
#include <complex>
#include <vector>
using namespace std;

typedef long long gtype;
typedef complex<gtype> point;
#define x real()
#define y imag()
#define crs(a, b) ( (conj(a) * (b)).y )

long double polArea(vector<point> & p) {
	long double area = 0;
	for (size_t i = 0; i < p.size() - 1; ++i)
		area += crs(p[i], p[i + 1]);
	return abs(area) * 0.5;
}

long long gcd(long long a, long long b) {
	long long t;
	while (b)
		t = b, b = a % b, a = t;
	return a;
}

long long polLatticeB(vector<point> & p) {
	long long b = 0;
	for (size_t i = 1; i < p.size(); ++i)
		b += gcd(abs(p[i].y - p[i - 1].y), abs(p[i].x - p[i - 1].x));
	return b;
}

int main() {
	int n;
	while (cin >> n && n) {
		// polygons
		vector<point> p(n + 1);
		for (int i = 0; i < n; ++i)
			cin >> p[i].x >> p[i].y;
		p[n] = p[0];
		// is convex
		cout << (long long) (polArea(p) - polLatticeB(p) * 0.5l + 1) << endl;
	}
	return 0;
}