#include #include #include #include #include using namespace std; /* * uses binary search to find best speed to ensure a given number of late projects */ const bool DEBUG = false; const int MAXOBJS = 21; const int MAXSEGS = 220; const double ZEROLIM = 1.0E-9; const double INTERSECTIONLIM = 1.0E-7; const double INF = 10000000000.0; const int SCREEN = 0; double speed = 1.0; // speed of balls, currently fixed at 1 cm/sec double tdiff = 1.0; // time between balls shot, currently fixed at 1 sec int nBalls; struct object { int count; // value inside object double removeT; // time object is removed }; object objects[MAXOBJS]; int nObjs; class pv // class for both point and vectors { public: double x, y; double length() { return sqrt(x*x+y*y); } void print(ostream& out) { out << '(' << x << ',' << y << ')'; } }; ostream& operator<<(ostream& out, pv p) {p.print(out); return out;} class segment { public: pv p1; // "first" endpoint pv a, n; // edge runs from p1 to p1+a; n = normal to a pointing away from object (normalized) int iObj; // index to object; void initSeg(int x1, int y1, int x2, int y2, int index) { p1.x = x1; p1.y = y1; a.x = x2-x1; a.y = y2-y1; n.x = -a.y; n.y = a.x; double len = sqrt(n.x*n.x + n.y*n.y); n.x /= len; n.y /= len; iObj = index; } pv reflection(const pv& a) { //cout << "reflection " << a << " on " << n << endl; pv aref = a; double dotProd = a.x*n.x + a.y*n.y; aref.x -= 2*dotProd*n.x; aref.y -= 2*dotProd*n.y; if (fabs(aref.x - (int)(aref.x+0.5)) < ZEROLIM) aref.x = (int)(aref.x+0.5); if (fabs(aref.y - (int)(aref.y+0.5)) < ZEROLIM) aref.y = (int)(aref.y+0.5); return aref; } }; segment segs[MAXSEGS]; int nSegs=0; class event { public: double thit; // time for next collision pv loc; // location of collision pv a; // vector coming into object int iSeg; // index of segment being hit }; class mycomparison { public: bool operator() (const event& lhs, const event&rhs) const { return (lhs.thit > rhs.thit); } }; priority_queue, mycomparison> pq; bool intersection(const segment& ball, const segment &s, double& t, double& u) // check for intersection of ball vector with segment s { //cout << "Intersection: ball = " << ball.p1 << ',' << ball.a << " and segment " << s.p1 << ',' << s.a << endl; double a = ball.a.x; double b = ball.a.y; double c = s.a.x; double d = s.a.y; double det = -a*d + b*c; if (abs(det) <= ZEROLIM) return false; double e = s.p1.x - ball.p1.x; double f = s.p1.y - ball.p1.y; u = (-e*b+f*a)/det; //cout << " u = " << u << endl; if (u < 0.0 || u > 1.0) return false; t = (-e*d + f*c)/det; //cout << " t = " << t << endl; return t > 0.0; } bool findNextIntersection(const segment& ball, int currSeg, double& t, double& u, int& iSeg) { //cout << "checking for intersection, time = " << time << endl; t=INF; bool found = false; for(int i=0; i 0) { // check if this object still exists after this collistion //if (iObj != 0) cout << " reflect (" << objects[iObj].count << ")" << endl; pv aReflect = segs[e.iSeg].reflection(e.a); segment tmp; tmp.p1 = e.loc; tmp.a = aReflect; if (findNextIntersection(tmp, e.iSeg, t, u, iSeg)) { double nextHitTime = e.thit+tmp.a.length()*t/speed; event nextEvent; nextEvent.thit = nextHitTime; nextEvent.loc.x = e.loc.x+t*tmp.a.x; nextEvent.loc.y = e.loc.y+t*tmp.a.y; nextEvent.a = tmp.a; nextEvent.iSeg = iSeg; //if (nextEvent.thit > 64 && nextEvent.thit < 66) cout <<" pushing event with time :" << nextEvent.thit << endl; pq.push(nextEvent); } } else { // must find next object (if any) //if (iObj != 0) cout << " go through" << endl; segment tmp; tmp.p1 = e.loc; tmp.a = e.a; if (findNextIntersection(tmp, -1, t, u, iSeg)) { double nextHitTime = e.thit+tmp.a.length()*t/speed; event nextEvent; nextEvent.thit = nextHitTime; nextEvent.loc.x = e.loc.x+t*tmp.a.x; nextEvent.loc.y = e.loc.y+t*tmp.a.y; nextEvent.a = tmp.a; nextEvent.iSeg = iSeg; //if (nextEvent.thit > 64 && nextEvent.thit < 66) cout <<" pushing event with time :" << nextEvent.thit << endl; pq.push(nextEvent); } } objects[SCREEN].count = 10; // make sure screen edges never disappear prevTime = e.thit; } } int filter(int a) { if (a < 0) return 0; return a; } int main() { int width, height, s, r; double loc; cin >> width >> height >> nBalls >> nObjs >> loc >> r >> s; // add three edges of screen segs[0].p1.x = 0; segs[0].p1.y = 0; segs[0].a.x = 0; segs[0].a.y = height; segs[0].n.x = 1; segs[0].n.y = 0; segs[0].iObj = SCREEN; segs[1].p1.x = 0; segs[1].p1.y = height; segs[1].a.x = width; segs[1].a.y = 0; segs[1].n.x = 0; segs[1].n.y = -1; segs[1].iObj = SCREEN; segs[2].p1.x = width; segs[2].p1.y = height; segs[2].a.x = 0; segs[2].a.y = -height; segs[2].n.x = -1; segs[2].n.y = 0; segs[2].iObj = SCREEN; objects[SCREEN].count = 10; // arbitrary non-zero value nSegs = 3; // process each object for(int i=1; i<=nObjs; i++) { int p; cin >> p; // # of segments int prevx, prevy; cin >> prevx >> prevy; for(int j=1; j> x >> y; segs[nSegs].initSeg(prevx, prevy, x, y, i); prevx = x; prevy = y; nSegs++; } segs[nSegs].initSeg(prevx, prevy, segs[nSegs-p+1].p1.x, segs[nSegs-p+1].p1.y, i); nSegs++; cin >> objects[i].count; objects[i].removeT = INF; } /* for(int i=0; i