#include #include using namespace std; const int MAXS = 125; const int MAXG = 100; const int MAXA = 100; const double PI = 4*atan(1.0); const double TOL = 0.000001; class edge { public: int w; int cap; edge *next; edge(int vert = -1, int capacity = 1, edge *nxt = 0) { w = vert; cap = capacity; next = nxt; } }; edge gr[MAXG+MAXA+2] = {0}; const int SOURCE = 0; int path[MAXG+MAXA+2] = {0}; int npath; int sink; bool printpath = false; bool findPath(int len, bool visited[]) { //if (len%50 == 0) //cout << len << endl; //if (printpath) { //for(int i=0; i<=len; i++) //cout << path[i] << ' '; //cout << endl; //} if (path[len] == sink) { npath = len; return true; } int v = path[len]; /* if (v == 117 || v == 87) { cout << "edges from " << v << " = "; for(edge* p = gr[v].next; p != 0; p = p->next) cout << p->w << ' '; cout << endl; } /**/ for(edge* p = gr[v].next; p != 0; p = p->next) { if (!visited[p->w]) { visited[p->w] = true; path[len+1] = p->w; if (findPath(len+1, visited)) return true; // visited[p->w] = false; } } return false; } bool findPath() { bool visited[sink+1]; for(int i=0; i<=sink; i++) visited[i] = false; return findPath(0, visited); } edge* findEdge(int v, int w) // // return prev edge to edge (v,w) { edge *p = gr+v; while (p->next != 0 && p->next->w != w) p = p->next; if (p->next == 0) return 0; return p; } int maxflow() { int flow = 0; while (findPath()) { /* for(int i=0; inext->cap == 0) { //cout << "deleting edge " << v << ',' << w << endl; edge* tmp = e->next; e->next = tmp->next; delete tmp; } e = findEdge(w, v); if (e == 0) { //cout << "adding edge " << w << ',' << v << endl; gr[w].next = new edge(v, 1, gr[w].next); } else ++e->next->cap; } } return flow; } struct wallseg { char type; int x, y; double cx, cy; double r; double ang1, ang2; int dx, dy; } segs[MAXS+1]; struct ga { int x, y; int level; } guards[MAXG], art[MAXA]; void printGraph(int ng) { for(int i=SOURCE; i<=sink; i++) { cout << i; if (i>SOURCE && i <= ng) cout << '(' << guards[i-1].x << ',' << guards[i-1].y << "):"; else if (i>ng && i < sink) cout << '(' << art[i-ng-1].x << ',' << art[i-ng-1].y << "):"; for(edge *p = gr[i].next; p != 0; p = p->next) cout << '(' << p->w<< ',' << p->cap << ')'; cout << endl; } } void setCircle(wallseg& seg, int x1, int y1, int x2, int y2, int dx, int dy) { double a = x2 -x1; double b = y2 - y1; double c = (x2*x2-x1*x1+y2*y2-y1*y1)/2.0; // ax+by=c eqn of line of points equidistant from (x1,y1) and (x2,y2) double d = dx; double e = dy; double f = d*x1+e*y1; // dx+ey=f eqn of line containing radius and (x1,y1) double den = a*e-b*d; if (den == 0) { cout << "ERROR: undefined circle starting at point " << x1 << ',' << y1 << endl; return; } seg.cx = (c*e - b*f)/den; seg.cy = (a*f - c*d)/den; seg.r = sqrt((seg.cx-x1)*(seg.cx-x1)+(seg.cy-y1)*(seg.cy-y1)); // determine range of angles seg.ang1 = atan2(y1-seg.cy, x1-seg.cx); // assume increasing from ang1 seg.ang2 = atan2(y2-seg.cy, x2-seg.cx); double zcross = (x1-seg.cx)*dy - (y1-seg.cy)*dx; if (zcross < 0) { // if z componet of cross product of radius vector with double tmp = seg.ang1; // tangent vector < 0, the decreasing from ang1 seg.ang1 = seg.ang2; seg.ang2 = tmp; } // if (seg.ang1 < 0) // don't think this is necesary // seg.ang1 += 2*PI; // if (seg.ang2 < 0) // seg.ang2 += 2*PI; } bool between(double a, double b, double c) { if (b < c) return (a >= b && a <= c); else return (a >= b || a <= c); } bool ok(double t, int sx, int sy, double dx, double dy, wallseg seg) { if (t < 0.0 || t > 1.0) // check if intersection is in line segment return false; double x = sx + t*dx; double y = sy + t*dy; //cout << " intersection at " << x << ',' << y << endl; // check if intersection is in arc double ang = atan2(y - seg.cy, x - seg.cx); return between(ang, seg.ang1, seg.ang2); } bool lineLineIntersect(int x1, int y1, int x2, int y2, wallseg seg) { //cout << "line check between " << x1 <<',' << y1 << " and " << x2 << ',' << y2 << " and " << seg.x <<',' << seg.y <<" and " << seg.x+seg.dx << ',' << seg.y+seg.dy << endl; double a = x2-x1; // solve at + bu = c double b = -seg.dx; // dt + eu = f double c = seg.x - x1; double d = y2-y1; double e = -seg.dy; double f = seg.y - y1; double denom = a*e - d*b; if (denom == 0) { // lines are parellel return false; // since in this case walls are connected, // we will detect an intersection on the // next or prev wall, so can just return // false here /* int v1 = a*y1+d*x1; if (a != 0) v1 /= a; else v1 /= d; int v2 = b*seg.y+e*seg.x; if (b != 0) v2 /= b; else v2 /= e; if (v1 != v2) return false; // not on same line // on same line, check for intersection if (max(x1, x2) < min(seg.x, seg.x+seg.dx) || min(x1, x2) > max(seg.x, seg.x+seg.dx)) return false; return !(max(y1, y2) < min(seg.y, seg.y+seg.dy) || min(y1, y2) > max(seg.y, seg.y+seg.dy)); /**/ } double t = (c*e-f*b)/denom; double u = (a*f-d*c)/denom; return (t >= 0.0 && t <= 1.0 && u >= 0.0 && u <= 1.0); } bool lineArcIntersect(int x1, int y1, int x2, int y2, wallseg seg) { //cout << "arc check between " << x1 <<',' << y1 << " and " << x2 << ',' << y2 << endl; double dx = x2-x1; double dy = y2-y1; double t1 = x1 - seg.cx; double t2 = y1 - seg.cy; double a = dx*dx + dy*dy; double b = 2*(t1*dx + t2*dy); double c = t1*t1+t2*t2-seg.r*seg.r; double disc = b*b - 4*a*c; //cout << " disc = " << disc << endl; if (fabs(disc) <= TOL) disc = 0.0; if (disc < 0.0) return false; t1 = (-b+sqrt(disc))/2/a; //cout << " t1 = " << t1 << endl; if (ok(t1, x1, y1, dx, dy, seg)) { if (disc != 0.0) return true; cout << "ERROR: line from guard to art too close to tangent line of arc" << endl; return false; } t2 = (-b-sqrt(disc))/2/a; //cout << " t2 = " << t2 << endl; if (ok(t2, x1, y1, dx, dy, seg)) { if (disc != 0.0) return true; cout << "ERROR: line from guard to art too close to tangent line of arc" << endl; return false; } return false; } void inputRoom(int offset, int ns) { for(int i=offset; i> segs[i].x >> segs[i].y >> segs[i].type; if (segs[i].type == 'c') cin >> segs[i].dx >> segs[i].dy; } segs[offset+ns] = segs[offset]; for(int i=offset; i> nr >> na >> ng; while (nr != 0) { int ns, tots = 0; for(int i=0; i> ns; inputRoom(tots, ns); tots += ns; } sink = na+ng+1; for(int i=0; i<=sink; i++) // fix later to delete all edges of previous graph gr[i] = 0; int target = 0; for(int i=0; i> art[i].x >> art[i].y >> art[i].level; target += art[i].level; gr[ng+i+1].next = new edge(sink, art[i].level, gr[ng+i+1].next); } for(int i=0; i> guards[i].x >> guards[i].y >> guards[i].level; gr[SOURCE].next = new edge(i+1, guards[i].level, gr[SOURCE].next); for(int j=0; j> nr >> na >> ng; } }