cake/CakeCutting_zeil.java

  1 import java.awt.geom.Point2D;
  2 import java.io.FileInputStream;
  3 import java.io.FileNotFoundException;
  4 import java.io.InputStream;
  5 import java.util.ArrayList;
  6 import java.util.HashMap;
  7 import java.util.Scanner;
  8 
  9 
 10 public class CakeCutting_zeil {
 11 
 12 
 13 
 14 
 15 	class Line {
 16 	  public Point2D.Double p1;
 17 	  public Point2D.Double p2;
 18 	  public int inputNumber;
 19 
 20 	  public Line() 
 21 	  {
 22 		  p1 = new Point2D.Double();
 23 		  p2 = new Point2D.Double();
 24 	  }
 25 
 26 	  public Line (Point2D.Double thruPoint1, Point2D.Double thruPoint2)
 27 	  {
 28 		  p1 = (Point2D.Double)thruPoint1.clone();
 29 		  p2 = (Point2D.Double)thruPoint2.clone();
 30 	  }
 31 	  
 32 	  public String toString()
 33 	  {
 34 		  return "[" + p1 + "," + p2 + "]";
 35 	  }
 36 
 37 	  double y(double x)
 38 	  {
 39 		  if (p1.x == p2.x)
 40 			  return Double.MAX_VALUE;
 41 		  else
 42 			  return (double)p1.y + ((double)(p2.y - p1.y) / (p2.x - p1.x)) * (x - p1.x);		  
 43 	  }
 44 	  
 45 	  double x(double y)
 46 	  {
 47 		  if (p1.y == p2.y)
 48 			  return Double.MAX_VALUE;
 49 		  else
 50 			  return  (double)p1.x + ( (double)(p2.x - p1.x) / (p2.y - p1.y)) * (y - p1.y);
 51 	  }
 52 
 53 		boolean parallel (Line line2)
 54 		{
 55 		  double c1 = (p2.y - p1.y) * (line2.p2.x - line2.p1.x);
 56 		  double c2 = (line2.p2.y - line2.p1.y) * (p2.x - p1.x);
 57 		  return c1 == c2;
 58 		}
 59 
 60 
 61 		Point2D.Double intersection (Line line2)
 62 		{
 63 			double rx = p2.x - p1.x;
 64 			double ry = p2.y - p1.y;
 65 			double sx = line2.p2.x - line2.p1.x;
 66 			double sy = line2.p2.y - line2.p1.y;
 67 			
 68 			double d = rx * sy - sx * ry;
 69 			double s = (-ry * (p1.x - line2.p1.x) + rx * (p1.y - line2.p1.y)) / d;
 70 		    double t = ( sx * (p1.y - line2.p1.y) - sy * (p1.x - line2.p1.x)) / d;
 71 			
 72 		    return new Point2D.Double(p1.x + (t * rx), p1.y + (t * ry));
 73 		}
 74 
 75 		double eval (Point2D.Double p)
 76 		{
 77 			double dx = p2.x - p1.x;
 78 			double dy = p2.y - p1.y;
 79 			double r = dx * (p.y - p1.y) - dy * (p.x - p1.x);
 80 			double scale = dx*dx + dy*dy;
 81 			return r / Math.sqrt(scale);
 82 		}
 83 
 84 
 85 	}
 86 
 87 
 88 
 89 	private Point2D.Double center;
 90 	private double radius;
 91 	private Line[] lines;
 92 	
 93 	
 94 	public class ApproxPoint {
 95 		public long x;
 96 		public long y;
 97 		
 98 		public ApproxPoint(Point2D.Double p) {
 99 			x = Math.round (1000.0 * p.x);
100 			y = Math.round (1000.0 * p.y);
101 		}
102 		
103 		public boolean equals (Object obj)
104 		{
105 			ApproxPoint p = (ApproxPoint)obj;
106 			return x == p.x && y == p.y;
107 		}
108 		
109 		public int hashCode ()
110 		{
111 			long k = 1301L * x + y;
112 			return (int)k;
113 		}
114 		
115 	}
116 	public class LinePair {
117 		int i;
118 		int j;
119 		
120 		LinePair (int i, int j) {
121 			this.i = i;
122 			this.j = j;
123 		}
124 	}
125 	
126 	HashMap<ApproxPoint, LinePair> priorIntersections;
127 
128 	public CakeCutting_zeil(int xc, int yc, int rc, int n, Scanner input) {
129 		center = new Point2D.Double(xc, yc);
130 		radius = rc;
131 		lines = new Line[n];
132 		for (int i = 0; i < n; ++i) {
133 			int x1, y1, x2, y2;
134 			x1 = input.nextInt();
135 			y1 = input.nextInt();
136 			Point2D.Double p1 = new Point2D.Double(x1, y1);
137 			x2 = input.nextInt();
138 			y2 = input.nextInt();
139 			Point2D.Double p2 = new Point2D.Double(x2, y2);
140 			lines[i] = new Line(p1, p2);
141 		}
142 		priorIntersections = new HashMap<>();
143 	}
144 
145 
146 
147 
148 
149 
150 
151 	void solve ()
152 	{
153 		int pieces = 1;
154 		// Discard any lines that do not intersect the circle
155 		ArrayList<Line> candidates = new ArrayList<>();
156 		for (int i = 0; i < lines.length; ++i)
157 		{
158 			lines[i].inputNumber = i;
159 			double d = lines[i].eval(center);
160 			if (Math.abs(d) < radius)
161 				candidates.add(lines[i]);
162 		}
163 		// Now count up the effects of the remaining lines
164 		for (int i = 0; i < candidates.size(); ++i) {
165 			++pieces;
166 			for (int j = 0; j < i; ++j) {
167 				Point2D.Double p = candidates.get(i).intersection(candidates.get(j));
168 				//System.out.format ( %.2f %.2f\n , p.x, p.y); // sjz
169 				if (p.distance(center) < radius) {
170 					// Intersection with other line is inside the circle
171 					++pieces;
172 					ApproxPoint ap = new ApproxPoint(p);
173 					LinePair prior = priorIntersections.get(ap);
174 					if (prior != null) {
175 						System.out.println ("*** Common intersections: lines " + candidates.get(i).inputNumber + " and " + candidates.get(j).inputNumber + " with " + prior.i + " and " + prior.j);
176 						System.out.println ("   " + candidates.get(i).inputNumber + ": " + candidates.get(i));
177 						System.out.println ("   " + candidates.get(j).inputNumber + ": " + candidates.get(j));
178 						System.out.println ("   intersect at " + p);
179 						System.out.println ("   " + prior.i + ": " + lines[prior.i]);
180 						System.out.println ("   " + prior.j + ": " + lines[prior.j]);
181 						System.out.println ("   intersect at " + lines[prior.i].intersection(lines[prior.j]));
182 
183 					}
184 					priorIntersections.put(ap, new LinePair(candidates.get(i).inputNumber, candidates.get(j).inputNumber));
185 				}
186 			}
187 		}
188 		System.out.println (pieces);
189 	}
190 
191 
192 
193 	
194 
195 	
196 	
197 	/**
198 	 * @param args
199 	 * @throws FileNotFoundException 
200 	 */
201 	public static void main(String[] args) throws FileNotFoundException {
202 		InputStream in = null;
203 		if (args.length > 0) {
204 			in = new FileInputStream(args[0]);
205 		} else {
206 			in = System.in;
207 		}
208 		Scanner input = new Scanner(in);
209 		int xc, yc, rc, n;
210 		while (true) {
211 			rc = input.nextInt();
212 			xc = input.nextInt();
213 			yc = input.nextInt();
214 			n = input.nextInt();
215 			if (rc == 0)
216 				break;
217 			new CakeCutting_zeil(xc, yc, rc, n, input).solve();
218 		}
219 	}
220 
221 
222 }