1 2 import java.io.*; 3 import java.util.*; 4 import java.awt.geom.*; 5 6 /** 7 * Solution to Cake Cutting 8 * 9 * Here's the key: Every line that crosses the circle creates one new section. 10 * Every time a line crosses another line inside the circle, it creates one new section. 11 * So, we've just got to count the number of lines that cross the circle 12 * and the number of line intersections that are inside the circle. 13 * 14 * @author vanb 15 */ 16 public class cake_vanb 17 { 18 public Scanner sc; 19 public PrintStream ps; 20 21 /** 22 * A Line, defined by two points. 23 * 24 * @author vanb 25 */ 26 public class Line 27 { 28 /** (x1,y1) and (x2,y2) */ 29 public int x1, y1, x2, y2; 30 31 /** 32 * Create a Line. 33 * 34 * @param x1 X coord of first point 35 * @param y1 Y coord of first point 36 * @param x2 X coord of second point 37 * @param y2 Y coors of second point 38 */ 39 public Line( int x1, int y1, int x2, int y2 ) 40 { 41 this.x1 = x1; 42 this.y1 = y1; 43 this.x2 = x2; 44 this.y2 = y2; 45 } 46 47 public String toString() 48 { 49 return "(" + x1 + "," + y1 + ") - (" + x2 + "," + y2 + ")"; 50 } 51 } 52 53 /** 54 * Driver. 55 * @throws Exception 56 */ 57 public void doit() throws Exception 58 { 59 sc = new Scanner( new File( "cake.judge" ) ); 60 ps = new PrintStream( new FileOutputStream( "cake.solution" ) ); 61 62 List<Line> lines = new LinkedList<Line>(); 63 64 HashSet<String> points = new HashSet<String>(); 65 66 int testcase = 0; 67 for(;;) 68 { 69 double r = sc.nextDouble(); 70 double xc = sc.nextDouble(); 71 double yc = sc.nextDouble(); 72 int n = sc.nextInt(); 73 if( r<0.5 ) break; 74 75 ++testcase; 76 77 // We always start with 1 - that's the circle itself 78 int count = 1; 79 lines.clear(); 80 for( int i=0; i<n; i++ ) 81 { 82 // Read in a line 83 int x1 = sc.nextInt(); 84 int y1 = sc.nextInt(); 85 int x2 = sc.nextInt(); 86 int y2 = sc.nextInt(); 87 88 // Find the closest point on the line to the center point of the circle 89 // 90 // First, express the line parametrically: 91 // x = x1 + (x2-x1)*t, y = y1 + (y2-y1)*t 92 // For convenience, we'll set dx=x2-x1, dy=y2-y1 93 // So, the parametric equations for the line become: 94 // x = x1 + dx*t, y = y1 + dx*t 95 // Note that when t=0, x=x1 and y=y1. When t=1, x=x2 and y=y2. 96 // If we were only interested in the line segment, then 0<=t<=1 97 // But, in this case, we're interested in the whole line. 98 double dx = x2-x1; 99 double dy = y2-y1; 100 101 // OK, now a trick: the smallest distance will also be the smallest distance squared. 102 // So, by minimizing distance squared instead of distance, we'll get the same 103 // answer, but we won't have to deal with that messy square root. 104 // 105 // Now, plugging our parametric equations into the distance (squared) formula, 106 // and doing some algebra, yields this, where (xc,yc) is the center of the circle: 107 // (dx^2+dy^2)*t^2 + 2*((x1-xc)*dx + (y1-yc)*dy)*t + (x1-xc)^2 + (y1-yc)^2 108 // We want to minimize this. Well, it's a quadratic in t, so it forms a nice parabola. 109 // The minimum will be at the bottom of the bowl, which is where the derivative is zero. 110 // So, take the derivative, set it equal to zero. 111 // 112 // 2*(dx^2+dy^2)*t + 2*((x1-xc)*dx + (y1-yc)*dy) = 0 113 // 114 // Solve for t, and we get this: 115 double t = -((x1-xc)*dx+(y1-yc)*dy) / (dx*dx+dy*dy); 116 117 // Now, we can get the (x,y) by just plugging t back into our parametric equations 118 double x = x1+dx*t; 119 double y = y1+dy*t; 120 121 // If the distance is less than the radius of the circle, 122 // then the line enters the circle, and cuts it. 123 // If not, then the line can be completely ignored. 124 if( Math.abs( Math.hypot(yc-y,xc-x) - r ) < 0.01 ) 125 { 126 System.err.println( "PANIC! Test case " + testcase + " has a line tangent to the circle!" ); 127 } 128 if( Math.hypot(yc-y,xc-x) < r ) 129 { 130 // Count it 131 ++count; 132 133 // Check for intersections with previous lines 134 for( Line line : lines ) 135 { 136 // We'll use Cramer's Rule to find the intersection. 137 // Cramer's Rule sez that, given two linear equations: 138 // a*x + b*y = c 139 // d*x + e*y = f 140 // Then the intersection is: 141 // 142 // |c b| |a c| 143 // |f e| |d f| 144 //x = ----- y = ----- 145 // |a b| |a b| 146 // |d e| |d e| 147 // 148 // Where each of those little boxes is the determinant of a 2x2 matrix, like so: 149 // |w x| 150 // |y z| = w*z - y*x 151 // 152 // So, 153 // c*e-f*b a*f-d*c 154 // x = ------- y = ------- 155 // a*e-d*b a*e-d*b 156 157 // Now, we've got to figure out a,b,c and d,e,f. 158 // We know that the equation of a line can be expressed as y = m*x + b, where m is the slope. 159 // m = (y2-y1)/(x2-x1). Multiplying by (x2-x1) gives us: 160 // (x2-x1)*y = (y2-y1)*x + K (where K is some constant we're not worried about yet.) 161 // So, 162 // (y2-y1)*x - (x2-x1)*y = -K 163 // And flip the x's to change the sign, 164 // (y2-y1)*x + (x1-x2)*y = -K 165 // 166 // So, a=y2-y1, b=x1-x2, and we can find c by just plugging in one of the points. 167 long a = y2-y1; 168 long b = x1-x2; 169 long c = a*x1 + b*y1; 170 171 // Do the same trick to find d,e,f from the other line 172 long d = line.y2-line.y1; 173 long e = line.x1-line.x2; 174 long f = d*line.x1 + e*line.y1; 175 176 // If the denominator is 0, then the lines are parallel and don't intersect. 177 // Because we've kept everything as integers so far, we can directly compare with 0. 178 // No chance of roundoff error, no need for an epsilon. 179 long denom = a*e - b*d; 180 if( denom!=0 ) 181 { 182 // Get the point of intersection, see if it's inside the circle. 183 x = (double)(c*e-f*b)/(double)denom; 184 y = (double)(a*f-d*c)/(double)denom; 185 if( Math.hypot(yc-y,xc-x) < r ) ++count; 186 187 if( Math.abs( Math.hypot(yc-y,xc-x) - r ) < 0.0001 ) 188 { 189 System.err.println( "PANIC! Test case " + testcase + " has an intersection on the circle!" ); 190 System.err.println( "r=" + r + ", xc=" + xc + ", yc=" + yc + ", n=" + n ); 191 } 192 String point = String.format( "%.2f %.2f", x, y ); 193 if( points.contains( point ) ) 194 { 195 System.err.println( "PANIC! Test case " + testcase + " has more than 2 lines intersecting at a single point!" ); 196 } 197 } 198 else 199 { 200 if( d*x1 + e*y1 == f ) 201 { 202 System.err.println( "PANIC! Test case " + testcase + " has coincident lines!" ); 203 } 204 } 205 } 206 207 // Add this line to the list of lines to compare future lines against 208 lines.add( new Line( x1, y1, x2, y2 ) ); 209 } 210 } 211 212 // Print the count! 213 ps.println( count ); 214 } 215 } 216 217 /** 218 * @param args 219 */ 220 public static void main( String[] args ) throws Exception 221 { 222 new cake_vanb().doit(); 223 224 // Random r = new Random(); 225 // for( int i=0; i<100; i++ ) 226 // { 227 // int rad = r.nextInt( 1000 ) + 1; 228 // int x = r.nextInt( 2001 ) - 1000; 229 // int y = r.nextInt( 2001 ) - 1000; 230 // int n = 1000; 231 // System.out.println( rad + + x + + y + + n ); 232 // 233 // for( int j=0; j<n; j++ ) 234 // { 235 // int x1 = r.nextInt( 2001 ) - 1000; 236 // int y1 = r.nextInt( 2001 ) - 1000; 237 // int x2 = r.nextInt( 2001 ) - 1000; 238 // int y2 = r.nextInt( 2001 ) - 1000; 239 // System.out.println( x1 + + y1 + + x2 + + y2 ); 240 // } 241 // } 242 } 243 }