10263 – Railway

A geometry distance computation problem.
You’re given N broken lines and a point M. Find the point S on the broken line that’s nearest to M.
The required point can be either on one end of a broken line segment, or it can be M’s projection on that segment. The rest is mere find-minimum computation. C++ implementation:

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

typedef long double gtype;
#define inRange(a, b, p, e) ( (p) >= min(a, b) - (e) && (p) <= max(a, b) + (e))
const gtype len_before_point_digits = 1E8;
const gtype epsLen = numeric_limits<gtype>::epsilon() * len_before_point_digits;
typedef complex<gtype> point;
#define x real()
#define y imag()
#define crs(a, b) ( (conj(a) * (b)).y )
#define intrN(a, b, p, q) ( crs((p)-(a),(b)-(a)) * (q) - crs((q)-(a),(b)-(a)) * (p) )
#define intrD(a, b, p, q) ( crs((p)-(a),(b)-(a)) - crs((q)-(a),(b)-(a)) )
#define pointDist(a, b, p) ( crs((b)-(a), (p)-(a)) / abs((b)-(a)) )
#define perp(p) ( point(-(p).y, (p).x) )
#define inRect(a, b, p, e) ( inRange((a).x, (b).x, (p).x, e) && inRange((a).y, (b).y, (p).y, e) )

void min(point* station, point p0, point p1, point m, gtype* minD) {
	// end points
	gtype d = abs(p1 - m);
	if (d <= *minD) {
		*minD = d;
		*station = p1;
	}
	// perp distance
	d = abs(pointDist(p0, p1, m));
	point v = perp(p1 - p0) + m;
	point r = intrN(p0, p1, m, v) / intrD(p0, p1, m, v);
	if (d <= *minD && inRect(p0, p1, r, epsLen)) {
		*minD = d;
		*station = r;
	}
}

int main() {
	cout.precision(4);
	int n;
	point m, start, p[2], station;
	while (cin >> m.x >> m.y) {
		gtype minD = numeric_limits<gtype>::max(), d;
		cin >> n;
		cin >> p[0].x >> p[0].y;
		start = point(p[0]);
		// start point
		d = abs(p[0] - m);
		if (d <= minD) {
			minD = d;
			station = p[0];
		}
		// broken line
		for (int i = 0; i < n; ++i) {
			cin >> p[1].x >> p[1].y;
			min(&station, p[0], p[1], m, &minD);
			p[0] = point(p[1]);
		}
		// end point
		min(&station, p[0], start, m, &minD);
		cout << fixed << station.x << endl << station.y << endl;
	}
	return 0;
}

920 – Sunny Mountains

A distance calculation geometry problem.
The illustrative figure makes the problem very simple. Sort the points according to their x co-ordinates. Iterate from left to right. Whenever a point (peak) rises higher than the previous highest peek, then the light is incident to it. What we need to do is accumulate the distance from the current peak to the bottom end of the lit part. So, the problem comes to an intersection task which is trivial given proper tools.
C++ implementation:

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

typedef long double gtype;
#define equ(a, b, e) ( abs((a) - (b)) <= (e) )
const gtype len_before_point_digits = 1E8;
const gtype epsLen = numeric_limits<gtype>::epsilon() * len_before_point_digits;
typedef complex<gtype> point;
#define x real()
#define y imag()
#define crs(a, b) ( (conj(a) * (b)).y )
#define intrN(a, b, p, q) ( crs((p)-(a),(b)-(a)) * (q) - crs((q)-(a),(b)-(a)) * (p) )
#define intrD(a, b, p, q) ( crs((p)-(a),(b)-(a)) - crs((q)-(a),(b)-(a)) )

bool cmp(point i, point j) {
	return i.x < j.x;
}

int main() {
	int nCase, nP;
	point p[128];
	cin >> nCase;
	cout.precision(2);
	while (nCase--) {
		// input
		cin >> nP;
		for (int i = 0; i < nP; ++i)
			cin >> p[i].x >> p[i].y;
		sort(p, p + nP, cmp);
		// solve
		gtype maxY = 0, red = 0;
		for (int i = nP - 2; i >= 0; --i) {
			// a peak that sees the sun
			if (maxY <= p[i].y) {
				gtype d = intrD(p[i], p[i + 1], point(0, maxY), point(1, maxY));
				if (!equ(d, 0, epsLen)) {
					point r = intrN(p[i], p[i + 1], point(0, maxY), point(1, maxY)) / d;
					red += abs(p[i] - r);
				}
				maxY = p[i].y;
			}
		}
		cout << fixed << red << endl;
	}
	return 0;
}

11068 – An Easy Task

A geometry problem.
After mirroring the plane along two lines, find the fixed point. If you think the problem thoroughly, it’ll be reduced to a line-line intersection problem. C++ implementation:

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

typedef long double gtype;
#define equ(a, b, e) ( abs((a) - (b)) <= (e) )
#define inRange(a, b, p, e) ( (p) >= min(a, b) - (e) && (p) <= max(a, b) + (e))
const gtype len_before_point_digits = 1E6;
const gtype epsLen = numeric_limits<gtype>::epsilon() * len_before_point_digits;

int main() {
	gtype p[2][3], d, x, y;
	cout.precision(2);
	while (cin >> p[0][0] >> p[0][1] >> p[0][2] >> p[1][0] >> p[1][1] >> p[1][2]) {
		if (p[0][0] == 0 && p[0][1] == 0 && p[0][2] == 0 && p[1][0] == 0 && p[1][1] == 0 && p[1][2] == 0)
			break;
		d = p[0][0] * p[1][1] - p[1][0] * p[0][1];
		if (equ(d, 0, epsLen)) {
			cout << "No fixed point exists." << endl;
		} else {
			x = (p[0][2] * p[1][1] - p[0][1] * p[1][2]) / d;
			y = (p[0][0] * p[1][2] - p[1][0] * p[0][2]) / d;
			if (equ(x, 0, epsLen))
				x = 0;
			if (equ(y, 0, epsLen))
				y = 0;
			cout << "The fixed point is at " << fixed << x << " " << y << "." << endl;
		}
	}
	return 0;
}

438 – The Circumference of the Circle

A circumcircle problem.
Given a triangle, find the circumference of its circumcircle. There’s an easy way and a hard way.
The hard way is to find the circle’s centre then calculate the radius. I used this solution for a previous problem. Code:

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

typedef long double gtype;
#define equ(a, b, e) ( abs((a) - (b)) <= (e) )
const gtype len_before_point_digits = 1E6;
const gtype epsLen = numeric_limits<gtype>::epsilon() * len_before_point_digits;
const gtype pi = M_PI;
typedef complex<gtype> point;
#define x real()
#define y imag()
#define crs(a, b) ( (conj(a) * (b)).y )
#define perp(p) ( point((p).y, -(p).x) )
#define intrN(a, b, p, q) ( crs((p)-(a),(b)-(a)) * (q) - crs((q)-(a),(b)-(a)) * (p) )
#define intrD(a, b, p, q) ( crs((p)-(a),(b)-(a)) - crs((q)-(a),(b)-(a)) )
#define circC(r) (2 * pi * abs(r))
#define plus(x) ((x) > 0 ? " + " : " - ")

int main() {
	point p[3], v[2][2], c;
	gtype r;
	cout.precision(2);
	while (cin >> p[0].x >> p[0].y >> p[1].x >> p[1].y >> p[2].x >> p[2].y) {
		// perp 1
		v[0][0] = 0.5l * (p[0] + p[1]);
		v[0][1] = perp(p[1] - p[0]) + v[0][0];
		// perp 2
		v[1][0] = 0.5l * (p[1] + p[2]);
		v[1][1] = perp(p[2] - p[1]) + v[1][0];
		// intersect
		gtype d = intrD(v[0][0], v[0][1], v[1][0], v[1][1]);
		if (!equ(d, 0, epsLen)) {
			c = intrN(v[0][0], v[0][1], v[1][0], v[1][1]) / d;
			r = abs(c - p[0]);
		} else
			r = 0;
		// out
		cout << fixed << circC(r) << endl;
	}
	return 0;
}

The easy way is to find the circumcircle’s radius through:


And since:



This method is less prone to error. Implementation:

#include <iostream>
#include <complex>
#include <limits>
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 )
#define circC(r) (2 * pi * abs(r))
#define area(a, b, c) ( (gtype) 0.5 * crs((b) - (a), (c) - (a)) )
#define plus(x) ((x) > 0 ? " + " : " - ")

int main() {
	point p[3];
	gtype r;
	cout.precision(2);
	while (cin >> p[0].x >> p[0].y >> p[1].x >> p[1].y >> p[2].x >> p[2].y) {
		r = abs(p[0] - p[1]) * abs(p[1] - p[2]) * abs(p[2] - p[0]) / area(p[0], p[1], p[2]) * 0.25;
		cout << fixed << circC(r) << endl;
	}
	return 0;
}

190 – Circle Through Three Points

A geometry problem.
Given three points, find the circle that passes though them. The problem statement illustrates what you have to do:
Given triangle , the circle centre is the intersection of the perpendicular bisectors on the sides. So, we need to find — the mid points of any two sides — and draw two perpendicular lines which intersect in the centre . The distance from to any point is the radius .
We need to transform this process into actual computation with vectors. A mid-point is easily determined. A perpendicular to a vector can be found by swapping the coordinates and negating only one of them. Intersection is also a simple task.






C++ implementation using some geometry tools:

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

typedef double gtype;
// const
const gtype len_before_point_digits = 1E6;
const gtype epsLen = numeric_limits<gtype>::epsilon() * len_before_point_digits;
// point
typedef complex<gtype> point;
#define x real()
#define y imag()
// vector
#define crs(a, b) ( (conj(a) * (b)).y )
#define perp(p) ( point((p).y, -(p).x) )
// line
#define intrN(a, b, p, q) ( crs((p)-(a),(b)-(a)) * (q) - crs((q)-(a),(b)-(a)) * (p) )
#define intrD(a, b, p, q) ( crs((p)-(a),(b)-(a)) - crs((q)-(a),(b)-(a)) )
// I/O
#define plus(x) ((x) > 0 ? " + " : " - ")

int main() {
	point p[3], v[2][2], c;
	gtype r;
	cout.precision(3);
	while (cin >> p[0].x >> p[0].y >> p[1].x >> p[1].y >> p[2].x >> p[2].y) {
		// perp 1
		v[0][0] = 0.5 * (p[0] + p[1]);
		v[0][1] = perp(p[1] - p[0]) + v[0][0];
		// perp 2
		v[1][0] = 0.5 * (p[1] + p[2]);
		v[1][1] = perp(p[2] - p[1]) + v[1][0];
		// intersect
		c = intrN(v[0][0], v[0][1], v[1][0], v[1][1]) / intrD(v[0][0], v[0][1], v[1][0], v[1][1]);
		r = abs(c - p[0]);
		// out
		gtype h = c.x, k = c.y;
		cout << fixed << "(x" << plus(-h) << abs(h) << ")^2 + (y" <<
				plus(-k) << abs(k) << ")^2 = " << r << "^2" << endl;
		gtype a = 2 * c.x, b = 2 * c.y, d = c.x * c.x + c.y * c.y - r * r;
		cout << fixed << "x^2 + y^2" << plus(-a) << abs(a) << "x" <<
				plus(-b) << abs(b) << "y" << plus(d) << abs(d) << " = 0" << endl;
		cout << endl;
	}
	return 0;
}