?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Adding some more judges, here and there.
[and.git] / NEERC / asteroids / asteroids_re.java
blob41241e28424355b848cc0eb4c2d57f0445788858
1 import java.io.*;
2 import java.util.*;
3
4 /**
5 * Solution for NEERC'2009 Problem A: Asteroids
6 * This solution checks correctness of the input.
7 * @author Roman Elizarov
8 */
9 public class asteroids_re {
10 static final boolean DEBUG = false;
11
12 public static void main(String[] args) throws Exception {
13 new asteroids_re().go();
14 }
15
16 void go() throws Exception {
17 read();
18 solve();
19 write();
20 }
21
22 static class V3D {
23 double x;
24 double y;
25 double z;
26
27 V3D(Scanner in) {
28 x = in.nextInt();
29 y = in.nextInt();
30 z = in.nextInt();
31 in.nextLine();
32 assert Math.abs(x) <= 10000;
33 assert Math.abs(y) <= 10000;
34 assert Math.abs(z) <= 10000;
35 }
36
37 @Override
38 public String toString() {
39 return "(" + x + "," + y + "," + z + ")";
40 }
41
42 boolean isZero() {
43 return x == 0 && y == 0 && z == 0;
44 }
45
46 double length() {
47 return Math.sqrt(x * x + y * y + z * z);
48 }
49
50 V3D(double x, double y, double z) {
51 this.x = x;
52 this.y = y;
53 this.z = z;
54 }
55
56 V3D add(V3D o) {
57 return new V3D(x + o.x, y + o.y, z + o.z);
58 }
59
60 V3D sub(V3D o) {
61 return new V3D(x - o.x, y - o.y, z - o.z);
62 }
63
64 V3D vec(V3D v) {
65 return new V3D(
66 y * v.z - z * v.y,
67 z * v.x - x * v.z,
68 x * v.y - y * v.x);
69 }
70
71 double dot(V3D v) {
72 return x * v.x + y * v.y + z * v.z;
73 }
74
75 V3D mul(double f) {
76 return new V3D(x * f, y * f, z * f);
77 }
78
79 V3D div(double f) {
80 return new V3D(x / f, y / f, z / f);
81 }
82 }
83
84 static class Face {
85 // n.dot(v) = d
86 V3D n;
87 double d;
88
89 final List<V3D> verts = new ArrayList<V3D>();
90
91 @Override
92 public String toString() {
93 return n.toString() + "," + d;
94 }
95
96 double side(V3D v) {
97 return n.dot(v) - d;
98 }
99
100 double angleBetween(V3D u, V3D v) {
101 V3D w = n.vec(u);
102 double sin = w.dot(v) / w.length() / v.length();
103 double cos = u.dot(v) / u.length() / v.length();
104 return Math.atan2(sin, cos);
105 }
106
107 public double dist(V3D v) {
108 return Math.abs(side(v) / n.length());
109 }
110 }
111
112 static class Polyhedra {
113 int n;
114 V3D[] verts;
115 final List<Set<Face>> vfaces = new ArrayList<Set<Face>>();
116 final List<Face> faces = new ArrayList<Face>();
117
118 Polyhedra(Scanner in) {
119 n = in.nextInt();
120 in.nextLine();
121 assert n >= 4 && n <= 60;
122 verts = new V3D[n];
123 for (int i = 0; i < n; i++) {
124 verts[i] = new V3D(in);
125 }
126 }
127
128 void buildFaces() {
129 for (int i = 0; i < n; i++) {
130 vfaces.add(new HashSet<Face>());
131 }
132 for (int i = 0; i < n; i++) {
133 for (int j = i + 1; j < n; j++) {
134 for (int k = j + 1; k < n; k++) {
135 checkFace(i, j, k);
136 }
137 }
138 }
139 if (DEBUG) {
140 List<Integer> flen = new ArrayList<Integer>();
141 for (Face face : faces) {
142 flen.add(face.verts.size());
143 }
144 Collections.sort(flen, Collections.reverseOrder());
145 System.out.println("FACES: " + flen);
146 }
147 assert faces.size() > 1; // non-degenerate!
148 for (Set<Face> vface : vfaces) {
149 assert !vface.isEmpty(); // convex! (each point on a face)
150 }
151 }
152
153 void checkFace(int i, int j, int k) {
154 if (!intersect(vfaces.get(i), vfaces.get(j), vfaces.get(k)).isEmpty())
155 return; // already on a common face
156 V3D w = verts[i];
157 V3D u = verts[j].sub(w);
158 V3D v = verts[k].sub(w);
159 final Face f = new Face();
160 f.n = u.vec(v);
161 assert !f.n.isZero(); // no 3 points on a line
162 f.d = f.side(w);
163 int side = 0;
164 List<Integer> indices = new ArrayList<Integer>();
165 for (int t = 0; t < n; t++) {
166 V3D tv = verts[t];
167 double tside = f.side(tv);
168 if (tside < 0) {
169 if (side > 0)
170 return; // not a face
171 side = -1;
172 } else if (tside > 0) {
173 if (side < 0)
174 return; // not a face
175 side = 1;
176 } else {
177 f.verts.add(tv);
178 indices.add(t);
179 }
180 }
181 if (side < 0) {
182 // make sure that "inside" has a positive value of side
183 f.n = f.n.mul(-1);
184 f.d = -f.d;
185 }
186 faces.add(f);
187 for (int t : indices) {
188 vfaces.get(t).add(f);
189 }
190 // sort verices on a face by angle
191 final V3D center = avg(f.verts);
192 final V3D v0 = w.sub(center);
193 assert Math.abs(f.side(center)) < 1; // just sanity check that center is on a plane
194 Collections.sort(f.verts, new Comparator<V3D>() {
195 public int compare(V3D o1, V3D o2) {
196 return Double.compare(f.angleBetween(v0, o1.sub(center)), f.angleBetween(v0, o2.sub(center)));
197 }
198 });
199 }
200
201 double solve() {
202 V3D v0 = avg(Arrays.asList(verts));
203 V3D vsum = new V3D(0, 0, 0);
204 double volume = 0;
205 for (Face face : faces) {
206 V3D v1 = face.verts.get(0);
207 for (int i = 2; i < face.verts.size(); i++) {
208 V3D v2 = face.verts.get(i - 1);
209 V3D v3 = face.verts.get(i);
210 double v = Math.abs(v1.sub(v0).vec(v2.sub(v0)).dot(v3.sub(v0)) / 6);
211 vsum = vsum.add(avg(Arrays.asList(v0, v1, v2, v3)).mul(v));
212 volume += v;
213 }
214 }
215 V3D center = vsum.div(volume); // center of mass
216 double min = Double.MAX_VALUE;
217 for (Face face : faces) {
218 min = Math.min(min, face.dist(center));
219 }
220 if (DEBUG) {
221 System.out.println("Center: " + center + "; Volume: " + volume + "; Min:" + min);
222 }
223 return min;
224 }
225
226 boolean containsAny(V3D[] verts) {
227 for (V3D vert : verts) {
228 if (contains(vert))
229 return true;
230 }
231 return false;
232 }
233
234 boolean contains(V3D v) {
235 for (Face face : faces) {
236 if (face.side(v) < -1e-6)
237 return false; // definitely outside
238 }
239 return true;
240 }
241 }
242
243 static V3D avg(List<V3D> verts) {
244 V3D sum = new V3D(0, 0, 0);
245 for (V3D v : verts) {
246 sum = sum.add(v);
247 }
248 return sum.div(verts.size());
249 }
250
251 static <T> Set<T> intersect(Set<T> a, Set<T> b, Set<T> c) {
252 Set<T> result = new HashSet<T>(a);
253 result.retainAll(b);
254 result.retainAll(c);
255 return result;
256 }
257
258 Polyhedra p;
259 Polyhedra q;
260
261 void read() throws Exception {
262 Scanner in = new Scanner(new File("asteroids.in"));
263 in.useLocale(Locale.US);
264 p = new Polyhedra(in);
265 q = new Polyhedra(in);
266 in.close();
267 }
268
269 double result;
270
271 void solve() {
272 p.buildFaces();
273 q.buildFaces();
274 assert !p.containsAny(q.verts);
275 assert !q.containsAny(p.verts);
276 result = p.solve() + q.solve();
277 }
278
279 void write() throws Exception {
280 PrintWriter out = new PrintWriter("asteroids.out");
281 out.println(result);
282 out.close();
283 }
284
285 //----------------- just for validation ------------------
286
287 /**
288 * Strict scanner to veryfy 100% correspondence between input files and input file format specification.
289 * It is a drop-in replacement for {@link java.util.Scanner} that could be added to a soulution source
290 * (cut-and-paste) without breaking its ability to work with {@link java.util.Scanner}.
291 */
292 public class Scanner {
293 private final BufferedReader in;
294 private String line = "";
295 private int pos;
296 private int lineNo;
297 private boolean localeset;
298
299 public Scanner(File source) throws FileNotFoundException {
300 in = new BufferedReader(new FileReader(source));
301 nextLine();
302 }
303
304 public void close() {
305 assert line == null : "Extra data at the end of file";
306 try {
307 in.close();
308 } catch (IOException e) {
309 throw new AssertionError("Failed to close with " + e);
310 }
311 }
312
313 public void nextLine() {
314 assert line != null : "EOF";
315 assert pos == line.length() : "Extra characters on line " + lineNo;
316 try {
317 line = in.readLine();
318 } catch (IOException e) {
319 throw new AssertionError("Failed to read line with " + e);
320 }
321 pos = 0;
322 lineNo++;
323 }
324
325 public String next() {
326 assert line != null : "EOF";
327 assert line.length() > 0 : "Empty line " + lineNo;
328 if (pos == 0)
329 assert line.charAt(0) > ' ' : "Line " + lineNo + " starts with whitespace";
330 else {
331 assert pos < line.length() : "Line " + lineNo + " is over";
332 assert line.charAt(pos) == ' ' : "Wrong whitespace on line " + lineNo;
333 pos++;
334 assert pos < line.length() : "Line " + lineNo + " is over";
335 assert line.charAt(0) > ' ' : "Line " + lineNo + " has double whitespace";
336 }
337 StringBuilder sb = new StringBuilder();
338 while (pos < line.length() && line.charAt(pos) > ' ')
339 sb.append(line.charAt(pos++));
340 return sb.toString();
341 }
342
343 public int nextInt() {
344 String s = next();
345 assert s.length() == 1 || s.charAt(0) != '0' : "Extra leading zero in number " + s + " on line " + lineNo;
346 assert s.charAt(0) != '+' : "Extra leading '+' in number " + s + " on line " + lineNo;
347 try {
348 return Integer.parseInt(s);
349 } catch (NumberFormatException e) {
350 throw new AssertionError("Malformed number " + s + " on line " + lineNo);
351 }
352 }
353
354 public double nextDouble() {
355 assert localeset : "Locale must be set with useLocale(Locale.US)";
356 String s = next();
357 assert s.length() == 1 || s.startsWith("0.") || s.charAt(0) != '0' : "Extra leading zero in number " + s + " on line " + lineNo;
358 assert s.charAt(0) != '+' : "Extra leading '+' in number " + s + " on line " + lineNo;
359 try {
360 return Double.parseDouble(s);
361 } catch (NumberFormatException e) {
362 throw new AssertionError("Malformed number " + s + " on line " + lineNo);
363 }
364 }
365
366 public void useLocale(Locale locale) {
367 assert locale == Locale.US;
368 localeset = true;
369 }
370 }
371 }