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
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
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
169 if (p.distance(center) < radius) {
170
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
199
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 }