10078 – The Art Gallery

Given a polygon shaped gallery, determine whether only one guard can observe the whole area.
This is merely a question of whether the polygon is convex or not. If there’s at least one reflex angle a, a guard placed on an adjacent angle to a will not be able to see the entire gallery because of a.

Convex check O(n)

Loop over perimeter and see if there’s any change in rotation direction.

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

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

bool polIsConvex(vector<point> & p) {
	int a[2] = { 0, 0 }, n = p.size() - 1;
	for (size_t i = 1; i < p.size(); ++i) {
		long double cross = crs(p[i % n] - p[i - 1], p[(i + 1) % n] - p[i - 1]);
		if (cross != 0)
			++a[cross > 0];
	}
	return !(a[0] && a[1]);
}

int main() {
	char answer[2][4] = { "Yes", "No" };
	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 << answer[polIsConvex(p)] << endl;
	}
	return 0;
}

Convex hull O(n log n)

Find the convex hull and compare both polygons.

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

typedef long double gtype;
const gtype pi = M_PI;
typedef complex<gtype> point;
#define x real()
#define y imag()
bool cmp_point(point const& p1, point const& p2) {
	return p1.x == p2.x ? (p1.y < p2.y) : (p1.x < p2.x);
}
#define crs(a, b) ( (conj(a) * (b)).y )

vector<point> mcH;
void monotoneChain(vector<point> &ps) {
	vector<point> p(ps.begin(), ps.end() - 1);
	int n = p.size(), k = 0;
	mcH = vector<point>(2 * n);
	sort(p.begin(), p.end(), cmp_point);
	for (int i = 0; i < n; i++) {
		while (k >= 2 && crs(mcH[k - 1] - mcH[k - 2], p[i] - mcH[k - 2]) < 0)
			k--;
		mcH[k++] = p[i];
	}
	for (int i = n - 2, t = k + 1; i >= 0; i--) {
		while (k >= t && crs(mcH[k - 1] - mcH[k - 2], p[i] - mcH[k - 2]) < 0)
			k--;
		mcH[k++] = p[i];
	}
	mcH.resize(k);
}

int main() {
	char answer[2][4] = { "Yes", "No" };
	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
		monotoneChain(p);
		cout << answer[mcH.size() == n + 1] << endl;
	}
	return 0;
}

Since is too small, there’s no much of a difference.

681 – Convex Hull Finding

Obviously, a convex hull problem. Tough, make sure that you sort the points w.r.t. y and build the hull in clockwise direction. I used the monotone chain algorithm.

#include <iostream>
#include <algorithm>
#include <complex>
#include <vector>
#include <limits>
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 )
bool cmp_point(point const& p1, point const& p2) {
	return p1.y == p2.y ? (p1.x < p2.x) : (p1.y < p2.y);
}

vector<point> mcH;
void monotoneChain(vector<point> &p) {
	int n = p.size(), k = 0;
	mcH = vector<point>(2 * n);
	sort(p.begin(), p.end(), cmp_point);
	for (int i = 0; i < n; i++) {
		while (k >= 2 && crs(mcH[k - 1] - mcH[k - 2], p[i] - mcH[k - 2]) <= 0)
			k--;
		mcH[k++] = p[i];
	}
	for (int i = n - 2, t = k + 1; i >= 0; i--) {
		while (k >= t && crs(mcH[k - 1] - mcH[k - 2], p[i] - mcH[k - 2]) <= 0)
			k--;
		mcH[k++] = p[i];
	}
	mcH.resize(k);
}

int main() {
	int nCase, n;
	vector<point> p;
	cin >> nCase;
	cout << nCase << endl;
	while (nCase-- && cin >> n) {
		// input & convex hull
		p.clear(), p.resize(n);
		for (int i = 0; i < n; ++i)
			cin >> p[i].x >> p[i].y;
		monotoneChain(p);
		// output
		cout << mcH.size() << endl;
		for (int i = 0; i < mcH.size(); ++i)
			cout << mcH[i].x << " " << mcH[i].y << endl;
		if (nCase) {
			cin >> n;
			cout << "-1\n";
		}
	}
	return 0;
}

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

259 – Software Allocation

You’re given 10 computers and a set of programs that need to be executed. A computer cannot multitask. Each problem needs to run on a computer of a specific set. Find an assignment of the programs to the computers.

We map the problem to a graph and solve via maximum flow.
We have two layers of nodes; those of the computers and those of the programs. Each computer node is connected to a program node if and only if it can run the program. The source node is connected to all 10 computer nodes and all program nodes are connected to the sink node.
We run Edmond-Karp algorithm and if the maximum flow is less that the number of programs, we can’t find a satisfactory allocation. Otherwise, an allocation is found and can be retrieved by examining the graph.
C++ implementaion with rank 217:

#include <algorithm>
#include <cstring>
#include <cstdio>
#include <limits>
#include <queue>
using namespace std;

#define N 39
int cap[N][N], parent[N], s = 37, t = 38;

bool bfs() {
	queue<int> q;
	q.push(s);
	memset(parent, -1, sizeof parent);
	parent[s] = s;
	while (q.size()) {
		int u = q.front();
		q.pop();
		if (u == t)
			return true;
		for (int v = 0; v < N; ++v)
			if (parent[v] == -1 && cap[u][v] > 0)
				parent[v] = u, q.push(v);
	}
	return false;
}

int maxFlow() {
	int mf = 0, f, v;
	while (bfs()) {
		// min
		v = t;
		f = numeric_limits<int>::max();
		while (parent[v] != v)
			f = min(f, cap[parent[v]][v]), v = parent[v];
		// update
		v = t;
		mf += f;
		while (parent[v] != v)
			cap[parent[v]][v] -= f, cap[v][parent[v]] += f, v = parent[v];
	}
	return mf;
}

int main() {
	char line[1024], *c, nProg = 1, mf;
	while (true) {
		// init
		memset(cap, 0, sizeof cap);
		for (int i = 0; i < 10; ++i)
			cap[i][t] = 1;
		// input
		nProg = 0;
		while (gets(line) && line[0]) {
			nProg += (cap[s][line[0] - 'A' + 10] = line[1] - '0');
			c = &line[3];
			while (*c != ';')
				cap[line[0] - 'A' + 10][*c - '0'] = 1, ++c;
		}
		// output
		if (!nProg)
			break;
		mf = maxFlow();
		if (mf == nProg)
			for (int i = 0; i < 10; ++i) {
				int j;
				for (j = 0; j < 26; ++j)
					if (cap[i][j + 10])
						break;
				printf("%c", j == 26 ? '_' : j + 'A');
			}
		else
			printf("!");
		printf("\n");
	}
	return 0;
}

1111 – Trash Removal

You’re required to find the minimum width of an arbitary polygon. The solution can be found in two steps:

• Find a convex hull that contains the polygon.
• Find it’s minimum width. I choose the Rotating Calipers to do this.

C++ rank 43:

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

typedef long double gtype;
const gtype pi = M_PI;
typedef complex<gtype> point;
#define x real()
#define y imag()
#define polar(r, t) polar((gtype) (r), (t))
// vector
#define rot(v, t) ( (v) * polar(1, t) )
#define crs(a, b) ( (conj(a) * (b)).y )
#define dot(a, b) ( (conj(a) * (b)).x )
#define pntLinDist(a, b, p) ( abs(crs((b)-(a), (p)-(a)) / abs((b)-(a))) )
bool cmp_point(point const& p1, point const& p2) {
	return p1.x == p2.x ? (p1.y < p2.y) : (p1.x < p2.x);
}

// O(n.log(n)) - monotone chain
vector<point> mcH;
void monotoneChain(vector<point> &ps) {
	vector<point> p(ps.begin(), ps.end() - 1);
	int n = p.size(), k = 0;
	mcH = vector<point>(2 * n);
	sort(p.begin(), p.end(), cmp_point);
	for (int i = 0; i < n; i++) {
		while (k >= 2 && crs(mcH[k - 1] - mcH[k - 2], p[i] - mcH[k - 2]) <= 0)
			k--;
		mcH[k++] = p[i];
	}
	for (int i = n - 2, t = k + 1; i >= 0; i--) {
		while (k >= t && crs(mcH[k - 1] - mcH[k - 2], p[i] - mcH[k - 2]) <= 0)
			k--;
		mcH[k++] = p[i];
	}
	mcH.resize(k);
}
// O(n) - rotating calipers (works on a ccw closed convex hull)
gtype rotatingCalipers(vector<point> &ps) {
	int aI = 0, bI = 0;
	for (size_t i = 1; i < ps.size(); ++i)
		aI = (ps[i].y < ps[aI].y ? i : aI), bI = (ps[i].y > ps[bI].y ? i : bI);
	gtype minWidth = ps[bI].y - ps[aI].y, aAng, bAng;
	point aV = point(1, 0), bV = point(-1, 0);
	for (gtype ang = 0; ang < pi; ang += min(aAng, bAng)) {
		aAng = acos(dot(ps[aI + 1] - ps[aI], aV)
			/ abs(aV) / abs(ps[aI + 1] - ps[aI]));
		bAng = acos(dot(ps[bI + 1] - ps[bI], bV)
			/ abs(bV) / abs(ps[bI + 1] - ps[bI]));
		aV = rot(aV, min(aAng, bAng)), bV = rot(bV, min(aAng, bAng));
		if (aAng < bAng)
			minWidth = min(minWidth, pntLinDist(ps[aI], ps[aI] + aV, ps[bI]))
			, aI = (aI + 1) % (ps.size() - 1);
		else
			minWidth = min(minWidth, pntLinDist(ps[bI], ps[bI] + bV, ps[aI]))
			, bI = (bI + 1) % (ps.size() - 1);
	}
	return minWidth;
}

int main() {
	int caseI = 0, n;
	vector<point> p;
	cout.precision(2);
	while (cin >> n && n) {
		p.clear(), p.resize(n + 1);
		// input
		for (int i = 0; i < n; ++i)
			cin >> p[i].x >> p[i].y;
		p[n] = p[0];
		// solve
		monotoneChain(p);
		if (caseI)
			cout << endl;
		cout << "Case " << ++caseI << ": " << fixed << rotatingCalipers(mcH);
	}
	return 0;
}