// 10310.cpp http://acm.uva.es/p/v103/10310.html // // Solution to ACM problem #10310 - "Dog and Gopher" // // Matthew Eagar - meagar@gmail.com // Verified to work as of April 30 / 2005 // // Updated for Standards compliance August 20 / 2005 // Updated to use Point struct July 24 / 2009 // #include #include #include #include struct Point { float x, y; inline float sqr(float x) const { return x * x; } // Returns the distance squared (avoid sqrt() for speed) float dist2(const Point& p) const { return sqr(x - p.x) + sqr(y - p.y); } }; std::istream& operator>>(std::istream& in, Point& p) { return in >> p.x >> p.y; } std::ostream& operator<<(std::ostream& out, const Point& p) { return out << '(' << p.x << ',' << p.y << ')'; } int main() { int n; std::cout << std::setiosflags(std::ios::fixed); std::cout << std::setprecision(3); Point goph, dog, hole; while (std::cin >> n >> goph >> dog) { bool done = false; while (--n >= 0 && std::cin >> hole) { if (done) continue; // gopher has already escaped // If the dog is at least twice as far from the hole... // (dist * 4) because of missing sqrt() calls if (hole.dist2(goph) * 4 <= hole.dist2(dog)) { // ...the gopher can safely reach it std::cout << "The gopher can escape through the hole at " << hole << ".\n"; done = true; } } // None of the holes were close enough if (!done) std::cout << "The gopher cannot escape." << std::endl; } }