// Tom Wexler import java.util.*; import java.io.*; public class I { public static void main(String[] args) { Scanner input = new Scanner(System.in); int caseNo = 1; int w = input.nextInt(); int a = input.nextInt(); int g = input.nextInt(); while(w > 0 || a > 0 || g > 0) { int[] aLev = new int[a]; v2[] aPos = new v2[a]; int[] gLev = new int[g]; v2[] gPos = new v2[g]; int totalArt = 0; ArrayList lines = new ArrayList(); ArrayList arcs = new ArrayList(); // read in walls for(int i = 0; i < w; i++) { int m = input.nextInt(); int xs = input.nextInt(); int ys = input.nextInt(); int x1 = xs; int y1 = ys; int xt = 0; int yt = 0; String str = input.next(); if (str.charAt(0) == 'c') { xt = input.nextInt(); yt = input.nextInt(); } for(int j = 1; j < m; j++) { int x2 = input.nextInt(); int y2 = input.nextInt(); if (str.charAt(0) == 'c') { arcs.add(new arc(new v2(x1,y1), new v2(x2,y2), new v2(xt,yt))); } else { lines.add(new line(new v2(x1,y1), new v2(x2,y2))); } x1 = x2; y1 = y2; str = input.next(); if (str.charAt(0) == 'c') { xt = input.nextInt(); yt = input.nextInt(); } } if (str.charAt(0) == 'c') { arcs.add(new arc(new v2(x1,y1), new v2(xs,ys), new v2(xt,yt))); } else { lines.add(new line(new v2(x1,y1), new v2(xs,ys))); } } // read in art for(int i = 0; i < a; i++) { aPos[i] = new v2(input.nextInt(), input.nextInt()); aLev[i] = input.nextInt(); totalArt = totalArt + aLev[i]; } // read in guards for(int i = 0; i < g; i++) { gPos[i] = new v2(input.nextInt(), input.nextInt()); gLev[i] = input.nextInt(); } // build G int n = a+g+2; int[][] G = new int[n][n]; for(int i = 0; i < g; i++) { G[0][i+1] = gLev[i]; // guard i is node i+1 } for(int j = 0; j < a; j++) { G[j+1+g][n-1] = aLev[j]; // art j is node j+1+g } for(int i = 0; i < g; i++) { for(int j = 0; j < a; j++) { if (LOS(gPos[i],aPos[j],arcs,lines)) { G[i+1][j+1+g] = 1; } } } // solve problem System.out.print("Case "+caseNo+": "); //System.out.println(maxFlow(G)+" " + totalArt); if (maxFlow(G) >= totalArt) System.out.println("Yes"); else System.out.println("No"); // start next instance w = input.nextInt(); a = input.nextInt(); g = input.nextInt(); // System.out.println(w+" "+a+" "+g); caseNo++; } } public static boolean LOS(v2 p1, v2 p2, ArrayList arcs, ArrayList lines) { for(arc a : arcs) { if (a.testIntersect(p1,p2)) return false; } for(line l2 : lines) { if (l2.testIntersect(p1,p2)) return false; } return true; } public static int maxFlow(int[][] cap) { int n = cap.length; int flowVal = 0; int[][] flow = new int[n][n]; int[] prev = new int[n]; boolean pathExists = true; while(pathExists) { Arrays.fill(prev, -1); LinkedList queue = new LinkedList(); queue.add(0); while(!queue.isEmpty() && prev[n-1] == -1) { int v = queue.poll(); for (int x = 0; x < n; x++) { if (prev[x] == -1 && (flow[v][x] < cap[v][x] || flow[x][v] > 0)) { prev[x] = v; queue.add(x); } } } if (prev[n-1] == -1) { pathExists = false; } else { int v = n-1; int u = prev[n-1]; while(v != 0) { // edge goes from u to v if (flow[v][u] > 0) flow[v][u]--; else flow[u][v]++; v = u; u = prev[v]; } flowVal++; } } return flowVal; } } class line { double a,b,c; v2 point1, point2; public line(v2 point1, v2 point2) { this.point1 = point1; this.point2 = point2; a = point2.y - point1.y; b = point1.x - point2.x; c = a*point1.x + b*point1.y; } public v2 intersect(line l) { double det = a*l.b - l.a*b; return new v2((l.b*c-b*l.c)/det, (a*l.c-l.a*c)/det); } public boolean testIntersect(line l) { double det = a*l.b - l.a*b; if (det == 0) return false; v2 intPt = new v2((l.b*c-b*l.c)/det, (a*l.c-l.a*c)/det); //System.out.println(intPt); return (((point1.minus(intPt).dot(point2.minus(intPt))) < 0) && (l.point1.minus(intPt).dot(l.point2.minus(intPt)) < 0)); } public boolean testIntersect(v2 p1, v2 p2) { return testIntersect(new line(p1,p2)); } } class v2 { double x; double y; public v2(double x, double y) { this.x = x; this.y = y; } // project this vector onto vector b public v2 proj(v2 b) { return b.scale(this.dot(b)/b.dot(b)); } public v2 scale(double s) { return new v2(x*s, y*s); } public double dot(v2 b) { return x*b.x+y*b.y; } public v2 plus(v2 b) { return new v2(x+b.x, y+b.y); } public v2 minus(v2 b) { return new v2(x-b.x, y-b.y); } public double mag2() { return x*x+y*y; } public double mag() { return Math.sqrt(mag2()); } public String toString() { return "("+x+","+y+")"; } public v2 rot90() { return new v2(y,-x); } } class arc { v2 start; v2 end; v2 tan; v2 center; double rsq; public arc(v2 start, v2 end, v2 tan) { this.start = start; this.end = end; this.tan = tan; v2 midpt = start.plus(end).scale(.5); line mirror = new line(midpt, midpt.plus(start.minus(end).rot90())); line spoke = new line(start, start.plus(tan.rot90())); center = mirror.intersect(spoke); rsq = center.minus(start).mag2(); //System.out.println(center+" "+rsq); } public boolean testIntersect(v2 a, v2 b) { // if the line doesn't hit the circle, return false v2 shiftv = a.minus(b); v2 shiftc = center.minus(b); v2 closest = shiftc.proj(shiftv).plus(b); if (closest.minus(center).mag2() > rsq) return false; double asqr = closest.minus(center).mag2(); double l = Math.sqrt(rsq - asqr); v2 offset = shiftv.scale(l/shiftv.mag()); // Intersection points of the line and the circle v2 sol1 = closest.plus(offset); v2 sol2 = closest.minus(offset); v2 circStart = start.minus(center); v2 circEnd = end.minus(center); v2 circSol1 = sol1.minus(center); v2 circSol2 = sol2.minus(center); // Ordering of points along the arc. double rank1 = circStart.dot(circSol1); double rank2 = circStart.dot(circSol2); double rankEnd = circStart.dot(circEnd); if (circSol1.dot(tan) < 0) rank1 = - rank1 - 2*circStart.mag2(); if (circSol2.dot(tan) < 0) rank2 = - rank2 - 2*circStart.mag2(); if (circEnd.dot(tan) < 0) rankEnd = - rankEnd - 2*circStart.mag2(); //boolean inters = false; if (sol1.minus(a).dot(sol1.minus(b)) < 0 && rankEnd < rank1) { //System.out.println(sol1 + " is an intersect"); //inters = true; return true; } if (sol2.minus(a).dot(sol2.minus(b)) < 0 && rankEnd < rank2) { //System.out.println(sol2 + " is an intersect"); //inters = true; return true; } //System.out.println(circStart.mag2() + " "+ circEnd.mag2() + " " + circSol1.mag2() + " " + circSol2.mag2()); // if a and b lie on the same segment of the line split by the circle, return false // check whether they are within the arc //return inters; return false; } }