/* NWERC 2008: Sample solution to "Wildwater Rafting" * Author: Per Austrin * * Algorithm: brute force */ #include #include #include using namespace std; struct P { double x, y; P(double x=0, double y=0): x(x), y(y) {} P operator-(P p) const { return P(x-p.x, y-p.y); } P operator*(double f) const { return P(f*x, f*y); } double dot(const P& p) { return x*p.x + y*p.y;} double dist2() { return dot(*this); } }; double d(P p0, P p1, P q) { double t = 0 >? (p1-p0).dot(q-p0) / (p1-p0).dist2()