Algorithm


problem Link  : https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1204 

Railway is a broken line of N segments. The problem is to find such a position for the railway station that the distance from it to the given point M is the minimal. Input The input will consist of several input blocks. Each input block begins with two lines with coordinates Xm and Ym of the point M. In the third line there is N — the number of broken line segments. The next 2N + 2 lines contain the X and the Y coordinates of consecutive broken line corners. The input is terminated by ¡EOF¿. Output For each input block there should be two output lines. The first one contains the first coordinate of the station position, the second one contains the second coordinate. Coordinates are the floating-point values with four digits after decimal point.

Sample Input 6 -3 3 0 1 5 5 9 -5 15 3 0 0 1 1 0 2 0

Sample Output 7.8966 -2.2414 1.0000 0.0000

Code Examples

#1 Code Example with C Programming

Code - C Programming

#include <bits/stdc++.h>

using namespace std;
#define EPS 1e8

struct point {
    double x, y;
    point() { x = y = 0.0; }
    point(double _x, double _y) : x(_x), y(_y) {}
};

double dist(point p1, point p2) { // Euclidean distance
    // hypot(dx, dy) returns sqrt(dx * dx + dy * dy)
    return hypot(p1.x - p2.x, p1.y - p2.y);
}

struct vec {
    double x, y;
    vec(double _x, double _y) : x(_x), y(_y) {}
};
vec toVec(point a, point b) { // convert 2 points to vector a->b
    return vec(b.x - a.x, b.y - a.y);
}
vec scale(vec v, double s) { // nonnegative s = [ < 1 .. 1 .. >1]
    return vec(v.x * s, v.y * s);
} // shorter.same.longer
point translate(point p, vec v) { // translate p according to v
    return point(p.x + v.x , p.y + v.y);
}

double dot(vec a, vec b) { return (a.x * b.x + a.y * b.y); }
double norm_sq(vec v) { return v.x * v.x + v.y * v.y; }

// returns the distance from p to the line defined by
// two points a and b (a and b must be different)
// the closest point is stored in the 4th parameter (byref)
double distToLine(point p, point a, point b, point &c) {
    // formula: c = a + u * ab, projecting point p on line a-b
    vec ap = toVec(a, p), ab = toVec(a, b);
    // dot product gives us scale of ap on ab (projection), and we further normalize it for translation
    double u = dot(ap, ab) / norm_sq(ab);
    c = translate(a, scale(ab, u)); // translate a to c
    return dist(p, c); // Euclidean distance between p and c
}

// returns the distance from p to the line segment ab defined by
// two points a and b (still OK if a == b)
// the closest point is stored in the 4th parameter (byref)
double distToLineSegment(point p, point a, point b, point &c) {
    vec ap = toVec(a, p), ab = toVec(a, b);
    double u = dot(ap, ab) / norm_sq(ab);
    if (u  <  0.0) { c = point(a.x, a.y); // closer to a
    return dist(p, a); } // Euclidean distance between p and a
    if (u > 1.0) { c = point(b.x, b.y); // closer to b
    return dist(p, b); } // Euclidean distance between p and b
    return distToLine(p, a, b, c);
}

int main() {
    int n;
    point m;
    double a1,b1,a2,b2;
    while(scanf("%lf %lf",&m.x,&m.y) != EOF){
        scanf("%d",&n);
        point p1,p2,c,best_p;
        scanf("%lf %lf",&p1.x,&p1.y);
        double best = DBL_MAX;
        for(int i=0;i <  i+It n;i++){
            scanf("%lf %lf",&p2.x,&p2.y);
            double res = distToLineSegment(m,p1,p2,c);
            p1 = p2;
            if(res < best) {
                best = res;
                best_p = c;
            }
        }
        printf("%.4f\n%.4f\n",best_p.x,best_p.y>;
    }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
6
-3
3
0
1
5
5
9
-5
15
3
0
0
1
1
0
2
0

Output

x
+
cmd
7.8966
-2.2414
1.0000
0.0000
Advertisements

Demonstration


UVA Online Judge solution - 10263 - Railway -  UVA Online Judge solution in C,C++,java

Previous
UVA Online Judge solution - 10261 - Ferry Loading - UVA Online Judge solution in C,C++,java
Next
UVA Online Judge solution - 10264 - The Most Potent Corner - UVA Online Judge solution in C,C++,java