Problem A: Railway

Problem

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




Olga Zaverach, 2002

這個點可能是投影點, 但因為投影點不一定在線段上, 因此需要特別判斷
#include <stdio.h>
#include <math.h>

double dist(double a, double b, double c, double d) {
    return (a-c)*(a-c)+(b-d)*(b-d);
}
int in(double a, double b, double c) {
    return (a >= b && a <= c) || (a <= b && a >= c);
}
int main() {
    double xm, ym;
    int n;
    while(scanf("%lf %lf", &xm, &ym) == 2) {
        scanf("%d", &n);
        double x[100], y[100];
        int i;
        for(i = 0; i <= n; i++)
            scanf("%lf %lf", x+i, y+i);
        double a, b, c, px, py, t;
        double mindist = dist(xm, ym, x[0], y[0]), ax, ay;
        double tmp;
        ax = x[0], ay = y[0];
        for(i = 0; i < n; i++) {
            a = y[i]-y[i+1], b = x[i]-x[i+1];
            b *= -1;
            c = -(a*x[i] + b*y[i]); // ax+by+c = 0
            t = (-a*xm-b*ym-c)/(a*a+b*b); //projection point (xm+t*a, ym+t*b)
            px = xm+t*a, py = ym+t*b;
            if(in(px, x[i], x[i+1]) && in(py, y[i], y[i+1])) {
                tmp = fabs(a*xm+b*ym+c)/sqrt(a*a+b*b);
                if(mindist > tmp)
                    mindist = tmp, ax = px, ay = py;
            }
            tmp = dist(xm, ym, x[i+1],y[i+1]);
            if(mindist > tmp)
                mindist = tmp, ax = x[i+1], ay = y[i+1];
        }
        printf("%.4lf\n%.4lf\n", ax, ay);
    }
    return 0;
}