10566 – Crossed Ladders

The problem is as shown in the figure. Given x, y, c, find d.

We can see that; given the distance between the two buildings d and the lengths of the ladders x & y, we can determisiticly find the hight of the intersection c.
However, we’re given x, y, c and required to find d. Thus, a binary search for d will do.

• We know that 0 <= d <= min(x,y)
• Given (x, y, d), we can find c'.
• If c' > c, we need more d. And vice versa.

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

typedef double gtype;
#define equ(a, b, e) ( abs((a) - (b)) <= (e) )
const gtype epsLen = 10E-6;
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 cosL(a, b, c) ( ((a) * (a) + (b) * (b) - (c) * (c)) / (2 * (a) * (b)) )

gtype getD(gtype x0, gtype y0, gtype d) {
	gtype y1, x1, intrDen;
	y1 = sqrt(y0 * y0 - d * d);
	x1 = sqrt(x0 * x0 - d * d);
	intrDen = intrD(point(0,0), point(d,x1), point(0,y1), point(d,0));
	if (equ(intrDen, 0, epsLen))
		return 0;
	return (intrN(point(0,0), point(d,x1), point(0,y1), point(d,0)) / intrDen).y;
}

int main() {
	cout.precision(3);
	gtype x0, y0, c0;
	while (cin >> x0 >> y0 >> c0) {
		gtype lD = 0, hD = min(x0, y0) + epsLen, mD;
		do {
			mD = (hD + lD) / 2.0;
			if (getD(x0, y0, mD) < c0)
				hD = mD;
			else
				lD = mD;
		} while (hD - lD > epsLen);
		cout << fixed << mD << endl;
	}
	return 0;
}

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

10451 – Ancient Village Sports

A surface area calculation problem.
A polygon’s area in term of its radius is:


The area of the outer circle is:

And the inner circle is:

Coded in C++:

#include <iostream>
#include <cmath>
using namespace std;

typedef long double gtype;
const gtype pi = 2 * acos(0);
#define polA(n) (((n) - 2) * pi / (n))

int main() {
	int caseI = 0;
	gtype Ap, n, rSqr, Ao, Ai, a;
	cout.precision(5);
	while (cin >> n >> Ap && n > 2) {
		a = pi - polA(n);
		rSqr = 2 * Ap / (n * sin(a));
		Ao = pi * rSqr;
		Ai = pi * rSqr * cos(a / 2) * cos(a / 2);
		cout << "Case " << ++caseI << ": ";
		cout << fixed << (Ao - Ap) << " " << (Ap - Ai) << endl;
	}
	return 0;
}

10432 – Polygon Inside A Circle

A polygon surface area calculation problem.
The formula for the regular n-gon’s area is:

And since the interior angle of a polygon is ,


C++ implementation:

#include <iostream>
#include <cmath>
using namespace std;

typedef long double gtype;
const gtype pi = M_PI;
#define polA(n) (((n) - 2) * pi / (n))

int main() {
	gtype r, n;
	cout.precision(3);
	while(cin >> r >> n)
		cout << fixed << (r * r * sin(polA(n)) * n * 0.5) << 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;
}