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