// Sonny's solution to pool // Stanford Local Programming Contest, October 2007 #include #include #include using namespace std; const double diam = 2.0; // vector/point class and a whole bunch of crap to go with it struct vec { double x, y; vec(double xx = 0, double yy = 0) : x(xx), y(yy) {}; double length() { return sqrt(x*x + y*y); } vec norm() { double len = length(); if (len > 0.0) return vec(x/len, y/len); else return vec(); } }; typedef vec point; istream &operator>>(istream &stream, vec &v) { stream >> v.x >> v.y; return stream; } bool operator==(const vec &a, const vec &b) { return a.x == b.x && a.y == b.y; } vec operator-(const vec &a, const vec &b) { return vec(a.x - b.x, a.y - b.y); } vec operator*(double s, const vec &v) { return vec(s*v.x, s*v.y); } double dot(const vec &a, const vec &b) { return a.x*b.x + a.y*b.y; } // distance between segment (a,b) and point c double segdist(const point &a, const point &b, const point &c) { vec v = b-a; if (v.x == 0.0 && v.y == 0.0) return (c - a).length(); double dp = (v.x*(c.x-a.x) + v.y*(c.y-a.y))/(v.x*v.x + v.y*v.y); dp = min(max(0.0, dp), 1.0); point p(v.x*dp + a.x, v.y*dp + a.y); return (c - p).length(); } int main() { // locations of the six pockets, renumbered 0 to 5... point pockets[6] = { point(0, 0), point(54, 0), point(108, 0), point(0,54), point(54,54), point(108,54) }; // read cue and target ball locations double cx, cy; point cue, target; while (1) { cin >> cx; if (cx == 0) break; cin >> cy >> target; cue = point(cx, cy); // read obstacle ball locations int n; cin >> n; vector balls(n); for (int i = 0; i < n; ++i) cin >> balls[i]; // iterate through the 6 pockets bool found = false; for (int p = 0; p < 6; ++p) { // determine the location of the point for cue to strike target vec d = (pockets[p] - target).norm(); point strike = target - diam*d; // TODO: Ascertain that this location is within the cushions? if (strike.x < 0.0 || strike.x > 108.0 || strike.y < 0.0 || strike.y > 54.0) // continue; cout << " " << n << "CUSHION "; // check shot direction double angle = dot((strike-cue).norm(), (pockets[p]-target).norm()); if (abs(angle) < 0.01) cout << " Angle warning [" << angle << "] "; if (angle <= 0.0) continue; // make sure the paths are clear of other balls bool clear = true; for (int b = 0; b < n; ++b) { double d1 = segdist(cue, strike, balls[b]); double d2 = segdist(target, pockets[p], balls[b]); if (abs(d1-diam) < 0.01) cout << " Distance warning [" << d1 << "] "; if (abs(d2-diam) < 0.01) cout << " Distance warning [" << d2 << "] "; if (d1 < diam || d2 < diam) { clear = false; break; } } if (clear) { if (found) cout << ' '; found = true; cout << p+1; } } if (!found) cout << "no shot"; cout << endl; } return 0; }