#include #include #include #include using namespace std; const int MAXG = 100; const float PI = 4.0*atan(1.0); const float INF = 1e10; class angleRange { public: float a1, a2; angleRange* next; angleRange(float aa1, float aa2, angleRange* n=0) : a1(aa1), a2(aa2), next(n) {} }; class edge { public: float perc; int w; edge* next; edge(int ww, float p, edge* n=0) : w(ww), perc(p), next(n) {} }; struct vertex { angleRange* alist; edge* list; float x, y, z, r; float v; float fillRate; float currFill; float t; bool done; } g[MAXG]; void printGraph(int n) { for(int i=0; inext) cout << " " << p->w << ',' << p->perc; cout << endl; } } float dist(float x1, float y1, float x2, float y2) { float dx = x1-x2; float dy = y1-y2; return sqrt(dx*dx+dy*dy); } void circleInt(float cx1, float cy1, float r1, float cx2, float cy2, float r2, float& ix1, float& iy1, float& ix2, float& iy2) { // expand (x-cx1)^2+(y-cy1)^2=r1^2 and the second circle equation, subtract to get a linear eqn in x and y, solve for y and put back into // first circle equation and solve for x if (cy1 != cy2) { float p1 = (r1*r1-cx1*cx1-cy1*cy1 - (r2*r2-cx2*cx2-cy2*cy2))/2.0; float p2 = (cx1-cx2)/(cy2-cy1); float p3 = p1/(cy2-cy1); float a = 1 + p2*p2; float b = -2*cx1 + 2*p2*p3 - 2*p2*cy1; float c = cx1*cx1 + p3*p3 - 2*p3*cy1 + cy1*cy1 - r1*r1; //cout << p1 << ' ' << p2 << ' ' << p3 << ' ' << a << ' ' << b << ' '<< c << endl; float disc = sqrt(b*b-4*a*c); ix1 = (-b+disc)/(2.0*a); iy1 = p2*ix1+p3; ix2 = (-b-disc)/(2.0*a); iy2 = p2*ix2+p3; } else { ix1 = ix2 = (r1*r1 - r2*r2- cx1*cx1 + cx2*cx2)/(cx2-cx1)/2.0; float disc = sqrt(r1*r1-(ix1-cx1)*(ix1-cx1)); iy1 = cy1+disc; iy2 = cy1-disc; } } void circleInt(float cx1, float cy1, float r1, float cx2, float cy2, float r2, float& a1, float& a2) { float ix1, iy1, ix2, iy2; circleInt(cx1, cy1, r1, cx2, cy2, r2, ix1, iy1, ix2, iy2); /* cout << '(' << ix1 << ',' << iy1 << ')' << endl; cout << '(' << ix2 << ',' << iy2 << ')' << endl; cout << (ix1-cx1)*(ix1-cx1) + (iy1-cy1)*(iy1-cy1) << endl; cout << (ix1-cx2)*(ix1-cx2) + (iy1-cy2)*(iy1-cy2) << endl; cout << (ix2-cx1)*(ix2-cx1) + (iy2-cy1)*(iy2-cy1) << endl; cout << (ix2-cx2)*(ix2-cx2) + (iy2-cy2)*(iy2-cy2) << endl; /**/ a1 = atan2(iy1-cy1, ix1-cx1); a2 = atan2(iy2-cy1, ix2-cx1); if (a1 > a2) swap(a1, a2); // perc = (a2-a1)/(2*PI); float x = cx1-r1; float y = cy1-0.01; if ((x-cx2)*(x-cx2)+(y-cy2)*(y-cy2)-r2*r2 < 0.0) { // check if -pi on circle 1 is inside circle 2 swap(a1, a2); // perc = 1 - perc; } } float calcPerc(int c1, float a1, float a2) { //cout << "a1, a2 = " << a1 << ',' << a2 << endl; if (a2 < a1) { return calcPerc(c1, -PI, a2) + calcPerc(c1, a1, PI); } else { angleRange* p1 = g[c1].alist; bool inside1 = false; float astart = a1; while (p1->next != 0 && a1 > p1->next->a2) p1 = p1->next; if (p1->next != 0 && a1 >= p1->next->a1) { inside1 = true; astart = p1->next->a2; } //cout << "astart = " << astart << endl; angleRange* p2 = p1->next; bool inside2 = true; float perc = 0.0; while (p2 != 0 && a2 > p2->a1) { if (p2->a1 > astart) // come back to look at this perc += p2->a1 - astart; astart = p2->a2; p2 = p2->next; } if (a2 > astart) { inside2 = false; perc += a2 - astart; //cout << " added " << a2-astart << " to perc" << endl; } //cout << "insides: " << inside1 << ',' << inside2 << endl; //cout << "p1, p2 values = " << p1->a1 << ',' << p2->a1 << endl; if (!inside1) p1->next = new angleRange(a1,a2, p1->next); p1 = p1->next; while (p1->next != p2) { angleRange* tmp = p1->next; p1->a2 = p1->next->a2; p1->next = p1->next->next; delete tmp; } if (!inside2) { p1->a2 = a2; } return perc/(2*PI); } } void getNextFillTime(int n, float& t, int& v) { t = INF; for(int i=0; i> n; for(int i=0; i> tmp.x >> tmp.y >> tmp.z >> tmp.r >> tmp.v; int j=i; while (j > 0 && g[j-1].z < tmp.z) { g[j] = g[j-1]; j--; } g[j] = tmp; g[j].alist = new angleRange(-1, -1); g[j].list = 0; g[j].fillRate = g[i].currFill = 0.0; g[j].t = INF; g[j].done = false; } for(int i=0; i= g[i].r+g[j].r || d + g[j].r <= g[i].r) // no intersect or lower contained in upper continue; if (d+g[i].r <= g[j].r) { // upper contained in lower a1 = -PI; a2 = PI; } else circleInt(g[i].x, g[i].y, g[i].r, g[j].x, g[j].y, g[j].r, a1, a2); perc = calcPerc(i, a1, a2); g[i].list = new edge(j, perc, g[i].list); /* cout << "i, j = " << i << ',' << j << ": perc = " << perc; for(angleRange* p = g[i].alist; p!= 0; p=p->next) cout << " (" << p->a1 << ',' << p->a2 << ")"; cout << endl; /**/ } } g[0].fillRate = 100.0; g[0].t = g[0].v/100.0; //printGraph(n); float lastt = 0.0, currt; int v; for(int i=0; iperc; g[w].t = currt + (g[w].v - g[w].currFill)/g[w].fillRate; } } } lastt = currt; } if (currt == INF) cout << "Invalid" << endl; else { printf("%.02f", currt); cout << endl; } // cout << currt << endl; }