/* Topcoder SRM 347, D1, 250-Pointer (Aircraft) James S. Plank September 26, 2010 */ #include #include #include #include #include using namespace std; class Aircraft { public: string nearMiss(vector p1, vector v1, vector p2, vector v2, int R); }; string Aircraft::nearMiss(vector p1, vector v1, vector p2, vector v2, int R) { vector x, y; double numerator; double den; double mint; double dr; int i; /* Convert R to a double, and square it */ dr = R; dr *= dr; /* Set x_i and y_i as advocated, to simplify the equations */ for (i = 0; i < p1.size(); i++) { x.push_back(p1[i]-p2[i]); y.push_back(v1[i]-v2[i]); } /* Differentiate, set to zero and solve for t. This will be in mint */ numerator = 0; den = 0; for (i = 0; i < x.size(); i++) numerator -= (x[i]*y[i]); for (i = 0; i < x.size(); i++) den += (y[i]*y[i]); mint = numerator / den; if (den == 0) mint = 0; if (mint < 0) mint = 0; /* Now that you have mint, go back and solve for the square of the distance. */ den = 0; for (i = 0; i < x.size(); i++) den += (x[i]*x[i]); for (i = 0; i < x.size(); i++) den += (2*x[i]*y[i]*mint); for (i = 0; i < x.size(); i++) den += (y[i]*y[i]*mint*mint); if (den <= dr) return "YES"; return "NO"; }