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;
}

199A – Hexadecimal’s theorem

The basic approach is:


Hence, if we generate the list of all Fibonacci numbers up to (input bound) the answer is just a binary-search-away.
C++ implementation:

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

typedef unsigned long long int64;
#define N 48

int64 fib[N];
int nFib;

int64 generate() {
	fib[0] = 0;
	fib[1] = 1;
	for (int i = 2; i < N; ++i)
		fib[i] = fib[i - 1] + fib[i - 2];
	return fib[N - 1];
}

int main(void) {
	generate();
	int64 n;
	cin >> n;
	int64 * p = upper_bound(fib, fib + N, n) - 1;
	if (p - 4 >= fib)
		cout << *(p - 4) << " " << *(p - 3) << " " << *(p - 1) << endl;
	else
		cout << "0 0 " << *p << endl;
	return EXIT_SUCCESS;
}

There’s an other naive (totally valid) solution. You noticed that 0 is a Fibonacci.

#include <stdio.h>
#include <stdlib.h>

int main(void) {
	int n;
	scanf("%d", &n);
	printf("0 0 %d\n", n);
	return EXIT_SUCCESS;
}

Ironic!!!