(UVA) 10263 - Railway

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=24&problem=1204

算是點到直線距離公式?!?

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

const double eps = 1e-9;
const double INF = 1e9 + 7;

double add(double a,double b) {
    if (abs(a+b) < eps * (abs(a) + abs(b))) return 0;
    else return a+b;
}

struct P {
    double x,y;
    P() {}
    P(double _x,double _y) : x(_x),y(_y) {}
    void pp() {
        cout<<"Point ("<<x<<","<<y<<")"<<endl;
    }
};

P MP(double x,double y) {
    return P{x,y};
}

P operator+(const P &p1,const P &p2) {
    return MP(add(p1.x,p2.x),add(p1.y,p2.y));
}

P operator-(const P &p1,const P &p2) {
    return MP(add(p1.x,-p2.x),add(p1.y,-p2.y));
}

P operator*(const double d,const P &p) {
    return MP(d*p.x,d*p.y);
}

double dot(const P &p1,const P &p2) {
    return add(p1.x*p2.x,p1.y*p2.y);
}

double cross(const P &p1,const P &p2) {
    return add(p1.x*p2.y,-p1.y*p2.x);
}

P intersection(P p1,P p2,P q1,P q2) {
    return p1 + cross(q1-p1,q2-q1)/cross(p2-p1,q2-q1)*(p2-p1);
}

bool on_seg(P p1,P p2,P q) {
    return cross(q-p1,q-p2)==0 && dot(q-p1,q-p2) <= 0;
}

int main () {
    P p;
    while (scanf("%lf",&p.x) != EOF) {
        scanf("%lf",&p.y);
        int n;
        scanf("%d",&n);
        P a;
        if (n>=1) scanf("%lf%lf",&a.x,&a.y);
        P ans;
        double mn = INF;
        while (n--) {
            P b;
            scanf("%lf%lf",&b.x,&b.y);
            double ax=b.y-a.y;
            double by=a.x-b.x;
            double c=a.y*b.x-a.x*b.y;
            double ret=abs(ax*p.x+by*p.y+c)/sqrt(ax*ax+by*by); //the smallest distance
            P inter = intersection(a,b,p,p-MP(ax,by));
            if (on_seg(a,b,inter)) {
                if (ret<mn) {
                    mn=ret;
                    ans = inter;
                }
            }
            else {
                if (sqrt(dot(p-a,p-a)) < mn) {
                    mn = sqrt(dot(p-a,p-a));
                    ans = a;
                }
                if (sqrt(dot(p-b,p-b)) < mn) {
                    mn = sqrt(dot(p-b,p-b));
                    ans = b;
                }
            }
            a=b;
        }
        printf("%.4f\n%.4f\n",ans.x,ans.y);
    }
}