#include #include #include #include #include using namespace std; /* * uses binary search to find best speed to ensure a given number of late projects */ const int MAXOBJS = 100; const int MAXSEGS = 1000; const double ZEROLIM = 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; 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 int ballNum; // ball number; double tprev; // previous hit time int iObjPrev; // index of previous object hit pv aNew; // reflected vector after collision double tdiff; // time between thit and next collision }; 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, double time, double& t, double& u, int& iSeg) { //cout << "checking for intersection, time = " << time << endl; t=INF; bool found = false; for(int i=0; i