#include #include #include #include #include #include #include #include #include using namespace std; typedef complex xy; typedef pair LineSegment; typedef vector polygon; typedef vector array; #define EPS (1.0e-9) #define ZEROP(x) (fabs(x)= 2); if (n + 1 == p.size()) return LineSegment(p.back(), p.front()); else return LineSegment(p[n], p[n + 1]); } void moveLineSegment(LineSegment* lsp, const xy& diff) { lsp->first += diff; lsp->second += diff; } xy diffVector(const LineSegment& ls) {return ls.second - ls.first;} bool isPoingOnLine(const xy& p, const LineSegment& ls) { xy u(diffVector(ls)), v(p - ls.first); return ZEROP(outerProduct(u, v)) && LE(0, innerProduct(u, v)) && LE(norm(v), norm(u)); } LineSegment extendE(const LineSegment& ls) { xy diff = diffVector(ls); diff /= abs(diff); const double epsilon = 5.0e-7; return LineSegment(ls.first - epsilon * diff, ls.second + epsilon * diff); } // solve lhs in (m1 m2)(lhs) = rhs. void inverseMatrix(const xy& m1, const xy& m2, const xy& rhs, xy* lhs) { double det = outerProduct(m1, m2); double x = + imag(m2) * real(rhs) - real(m2) * imag(rhs); double y = - imag(m1) * real(rhs) + real(m1) * imag(rhs); *lhs = xy(x / det, y / det); return; } int ccw(xy p1, xy p2, xy p3) { p2 -= p1; p3 -= p1; double op = outerProduct(p2, p3); if (LT(op, 0)) return -1; if (LT(0, op)) return 1; if (innerProduct(p2, p3)) return -1; if (LT(norm(p2), norm(p3))) return +1; return 0; } xy crossingPoint(const LineSegment& ls1, const LineSegment& ls2) { const xy diff(ls2.first - ls1.first); const xy u1(diffVector(ls1)); const xy u2(diffVector(ls2)); // solve t * u1 + s * u2 = diff; // then ls1.first + t * u1 = ls2.second - s * u2; // TODO: consider ls1 // ls2. To do so, return vector of xy. xy coe; inverseMatrix(u1, u2, diff, &coe); return ls1.first + real(coe) * u1; } bool isLineSegmentsCrossed(const LineSegment& ls1, const LineSegment& ls2, vector* points) { if (LE(ccw(ls1.first, ls1.second, ls2.first) * ccw(ls1.first, ls1.second, ls2.second), 0.0) && LE(ccw(ls2.first, ls2.second, ls1.first) * ccw(ls2.first, ls2.second, ls1.second), 0.0)) { points->push_back(crossingPoint(ls1, ls2)); return true; } return false; } bool inConvexPolygon(const polygon& po, const xy& p) { // First, check if p is online of any side of po. for (size_t i = 0; i < po.size(); ++i) if (isPoingOnLine(p, nthLineSegmentFromPolygon(po, i))) return true; // Next, check if p is wrapped. double small = outerProduct(po.back() - p, po.front() - p); double large = small; for (size_t i = 0; i + 1 < po.size(); ++i) { double prod = outerProduct(po[i] - p, po[i+1] - p); small = min(small, prod); large = max(large, prod); } return LT(0, small * large); } bool inConvexPolygonFalse(const polygon& po, const xy& p) { LineSegment ls(p, p + xy(10001, 1)); vector hoge; int count = 0; for (size_t i = 0; i < po.size(); ++i) { if (isLineSegmentsCrossed( nthLineSegmentFromPolygon(po, i), ls, &hoge)) { ++count; } } return count & 1; } struct Missile { LineSegment entity; xy velocity; Missile(){} Missile(double t, double xt, double vx, double vy, double length) { velocity = xy(vx, vy); xy pt(xt, 0); // head on t = t xy p0 = pt - t * velocity; xy q0 = p0 - length * velocity / abs(velocity); entity = LineSegment(p0, q0); } LineSegment moveTo(double t) const; }; LineSegment Missile::moveTo(double t) const { LineSegment result(entity); moveLineSegment(&result, t * velocity); return result; } struct MoveSequence { array timing; vector velocity; MoveSequence(){} MoveSequence(const array& t, const vector vel) :timing(t), velocity(vel) {} }; struct Princess { polygon position; MoveSequence ms; Princess(){} Princess(const polygon& p, const MoveSequence& ms) : position(p), ms(ms) {} polygon possitionAt(double t) const; }; polygon Princess::possitionAt(double t) const { polygon result; size_t i; xy shift(0, 0); for (i = 1; i < ms.timing.size() && ms.timing[i] < t; ++i) { shift += static_cast(ms.timing[i] - ms.timing[i - 1]) * ms.velocity[i]; } if (i < ms.timing.size()) { shift += ms.velocity[i] * (t - ms.timing[i - 1]); } for (size_t i = 0; i < position.size(); ++i) result.push_back(position[i] + shift); return result; } double hitMovingSegments(const LineSegment& ls1, xy v1, const LineSegment& ls2, xy v2) { xy v(v1 - v2); // make ls1 move in v, and make ls2 stand still. polygon para; // parallelogram. para.push_back(ls1.first); para.push_back(ls1.first + v); para.push_back(ls1.second + v); para.push_back(ls1.second); vector hit_points; if (inConvexPolygon(para, ls2.first)) hit_points.push_back(ls2.first); if (inConvexPolygon(para, ls2.second)) hit_points.push_back(ls2.second); for (size_t i = 0; i < 4; ++i) { isLineSegmentsCrossed( extendE(nthLineSegmentFromPolygon(para, i)), ls2, &hit_points); } if (hit_points.empty()) return -100; double earliest = 1e+10; for (size_t i = 0; i < hit_points.size(); ++i) { xy diff(hit_points[i] - ls1.first); // diff = s * (ls1.second-ls1.first) + t * v; 0<=s, t<=1 xy inv; inverseMatrix(diffVector(ls1), v, diff, &inv); double t = imag(inv); earliest = min(t, earliest); } return earliest; } double solveOneMissileOneSegment(const LineSegment& ls0, const MoveSequence& ms, const Missile& missile0) { LineSegment ls1(ls0); LineSegment mis_now(missile0.entity); double previous_time = 0; for (size_t i = 0; i < ms.timing.size(); ++i) { // ls1 moves in ms.velocity[i] // mis_now moves in missile0.velocity // calculate if they hits or not. double time_diff = ms.timing[i] - previous_time; double hit_time = hitMovingSegments(ls1, ms.velocity[i] * time_diff, mis_now, missile0.velocity * time_diff); // if hit, return it. if (hit_time > -1) { LOG() << "hit at " << i << " th move" << endl; return previous_time + time_diff * hit_time; } // if not, move ls1 and mis_now moveLineSegment(&ls1, time_diff * ms.velocity[i]); moveLineSegment(&mis_now, time_diff * missile0.velocity); previous_time = ms.timing[i]; } return -100; } double solveOneMissile(const Princess& p0, const Missile& missile0) { double earliest = 1.0e+20; for (size_t i = 0; i < p0.position.size(); ++i) { double hit = solveOneMissileOneSegment( nthLineSegmentFromPolygon(p0.position, i), p0.ms, missile0); if (hit > -1) { LOG() << "side #" << i << " with missile is hit at " << hit << endl; if (hit < earliest) earliest = hit; } } if (earliest < 1.0e+19) return earliest; else return -100; } vector solve(const Princess& p0, const vector& missile) { vector result; for (size_t i = 0; i < missile.size(); ++i) { LOG() << "start missile " << i << endl; double t = solveOneMissile(p0, missile[i]); if (t > -1) { result.push_back(t); } } sort(result.begin(), result.end()); return result; } bool readInput(Princess* pp, vector* missilep) { int nvertices, nmoves, nmissiles; while (cin >> nvertices >> nmoves >> nmissiles && nvertices > 0) { polygon me0; for (int i = 0; i < nvertices; ++i) { double x, y; cin >> x >> y; me0.push_back(xy(x, y)); } array timing; vector velocity; timing.push_back(0); velocity.push_back(xy(0, 0)); for (int i = 0; i < nmoves; ++i) { int t; double x, y; cin >> t >> x >> y; timing.push_back(t); velocity.push_back(xy(x, y)); } timing.push_back(2e+6); // > 10000 + 100 * 10000 velocity.push_back(xy(0, 0)); vector missile; for (int i = 0; i < nmissiles; ++i) { int t; double x, vx, vy, length; cin >> t >> x >> vx >> vy >> length; missile.push_back(Missile(t, x, vx, vy, length)); } *pp = Princess(me0, MoveSequence(timing, velocity)); *missilep = missile; return true; } return false; } void outputAnswer(const vector& hit) { cout << hit.size() << endl; cout.setf(ios::fixed); cout << setprecision(3); for (size_t i = 0; i < hit.size(); ++i) cout << hit[i] << endl; } void normalProgram() { Princess p; vector missile; int ncases = 0; while (readInput(&p, &missile)) { LOG() << "# case " << ++ncases << endl; vector hit(solve(p, missile)); outputAnswer(hit); } } #ifndef NODRIVER int main() { normalProgram(); return 0; } #endif