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