Tag: geometry

10078 – The Art Gallery

by MSiddeek, posted in Algorithms, Geometry, Problems

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 log(n) is too small, there’s no much of a difference.

    681 – Convex Hull Finding

    by MSiddeek, posted in Algorithms, Geometry, Problems

    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

    by MSiddeek, posted in Algorithms, Geometry, Problems

    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
    i = A - {B \over 2} + 1 Where

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

    All the reqired quantities are easily computable, however, B needs some extra work. To find the number of lattice points on line segment \{(x_1,y_1), (x_2,y_2)\} , we simply calculate GCD(|x_2-x_1|,|y_2-y_1|) .
    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;
}

    1111 – Trash Removal

    by MSiddeek, posted in Algorithms, Geometry, Problems

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

    218 – Moth Eradication

    by MSiddeek, posted in Algorithms, Geometry, Problems

    Given a set of points, find the polyong with minimum area that can contain these points.
    Solved by finding a convex hull using the monotone chain.

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

typedef long double 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.x == p2.x ? (p1.y < p2.y) : (p1.x < p2.x);
}

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 caseI = 0, n;
	vector<point> p;
	gtype perim;
	while (cin >> n && n) {
		// input & convex hull
		p.clear(), p.resize(n), perim = 0;
		for (int i = 0; i < n; ++i)
			cin >> p[i].x >> p[i].y;
		monotoneChain(p);
		// output
		if (caseI)
			cout << endl;
		cout << "Region #" << ++caseI << ":" << endl;
		cout.precision(1);
		cout << fixed << mcH[0];
		for (int i = 1; i < mcH.size(); ++i)
			cout << "-" << fixed << mcH[i], perim += abs(mcH[i] - mcH[i - 1]);
		cout.precision(2);
		cout << endl << "Perimeter length = " << fixed << perim << endl;
	}
	return 0;
}