import java.io.*; import java.util.*; /** * The Worm in the Apple * @author vanb * * There are two parts to this problem - first, finding the 3D convex hull of * a set of points, and then, finding a quick way to perform a lot of * 3D point-to-plane distance measurements for the queries. * * There are standard algorithms for 3D convex hull. If you don't know them, though, * you can still figure it out. This program uses the following technique: * * First, find the point with the smallest z. Translate this point to the origin. * * Then find the point which, from this point (which is now the origin), forms the * smallest angle. Think of the figure as a soccer ball. If we roll it in any direction, * which point hits first? That point, with our first point, has to form an edge * of the convex hull. For all the points (x,y,z), assuming that they've been translated * in the same way as p1, the point we're looking for is the one with the smallest * asin( z / sqrt(x^2+y^2+z^2) ). * * Once we find that point, rotate it in the XY plane (around the Z axis) so that it * lies above the positive X axis. Then, rotate it in the XZ plane (around the Y axis) so that * it lies ON the positive X axis. Now we have an edge with one point on the origin, and * the other on the positive X axis. * * Now, we need to find a third point, to form a triangular face of the convex hull. * Again, with our rolling soccer ball analogy, we'll find the point which forms the * smallest angle in the YZ plane. Once we do that, we'll have 3 vertices, 3 edges and 1 face. * * From here, the algorithm proceeds a lot like a Breadth-First Search. * We'll put edges on a queue, starting with the 3 from the first face that we just found. * Note that each edge forms a border between exactly 2 triangular faces. When we take * an edge off of the queue, we'll know one of the triangles (that's how the edge got on the * queue in the first place). If w don't know the other, we'll look for it. We'll use the * same trick we used before - translate so that one of the points is at the origin, rotate * so that the other is on the positive X axis, and then rotate so that the third point * of the known triangle lies in the XY plane (z=0) with a negative y. Then, the point * which forms the smallest angle with the XY plane is the third point of the other triangle. * That will give us a new face, and 2 new edges. * * After we've built the convex hull, we've got to perform the queries. For each query point, * We've got to go through all of the faces, and see which one it's closest to. If, as we * build the hull, we recorded the translation and rotation parameters to put the face in * the XY plane (z=0), then we can just apply them to the query point. Then, |z| is the distance * to the face. If the translated/rotated point isn't directly above the face, that's OK. It * won't be the minimum distance. The minimum distance has to be to a face that the point is * directly above (or below), when translated/rotated. */ public class worm { public Scanner sc; public PrintStream ps; public static final double TWOPI = Math.PI+Math.PI; public static final int MAX_VERTICES = 1000; public static final int MAX_QUERIES = 100000; /** * A Vertex - just a 3D coordinate. * @author vanb */ public class Vertex { // Coordinates public double x, y, z; /** * Set the value of this vertex by another vertex. * * @param v Another Vertex */ public void set( Vertex v ) { x = v.x; y = v.y; z = v.z; } /** * Translate this Vertex by delta X, delta Y, and delta Z. * * @param dx Delta X * @param dy Delta Y * @param dz Delta Z */ public void translate( double dx, double dy, double dz ) { x += dx; y += dy; z += dz; } /** * Rotate this Vertex in the XY plane (around the Z axis) * * @param a Angle of rotation */ public void rotatexy( double a ) { double oldx = x; double oldy = y; x = oldx*Math.cos( a ) - oldy*Math.sin( a ); y = oldx*Math.sin( a ) + oldy*Math.cos( a ); } /** * Rotate this Vertex in the XZ plane (around the Y axis) * * @param a Angle of rotation */ public void rotatexz( double a ) { double oldx = x; double oldz = z; x = oldx*Math.cos( a ) - oldz*Math.sin( a ); z = oldx*Math.sin( a ) + oldz*Math.cos( a ); } /** * Rotate this Vertex in the YZ plane (around the X axis) * * @param a Angle of rotation */ public void rotateyz( double a ) { double oldy = y; double oldz = z; y = oldy*Math.cos( a ) - oldz*Math.sin( a ); z = oldy*Math.sin( a ) + oldz*Math.cos( a ); } /** * The distance from this Vertex to the origin * * @return The distance from this Vertex to the origin */ public double length() { return Math.sqrt( x*x + y*y + z*z ); } /** * A pretty String for debugging * * @return A Pretty String for debugging */ public String toString() { return "[" + x + "," + y + "," + z + "]"; } } /** * This class represents a face of the 3D figure - or, rather, * the parameters to put that face flat on the XY plane (z=0) * with one of the points at the origin and another on the X axis, * @author vanb */ public class Face { // Changes in x, y and z to translate this face to the origin public double dx, dy, dz; // Rotations in the xy, xz, and yz planes public double xy, xz, yz; /** * Record the info for a Face * * @param dx X translation * @param dy Y translation * @param dz Z translation * @param xy Angle of rotation in the XY plane * @param xz Angle of rotation in the XZ plane * @param yz Angle of rotation in the YZ plane */ public Face( double dx, double dy, double dz, double xy, double xz, double yz ) { this.dx = dx; this.dy = dy; this.dz = dz; this.xy = xy; this.xz = xz; this.yz = yz; } } /** * This class represents an edge of the 3D figure. * The components (p1-p4) are indices into the Vertex array. * @author vanb */ public class Edge { // p1 and p2 are the vertices which form the endpoints // of this edge. if we know of one of the triangles that abut // this edge, then p3 is the other vertex of that triangle, // otherwise p3 is -1. If we know the second triangle which abuts // this edge, then p4 is the other vertex, otherwise p4 is -1. public int p1, p2, p3, p4; /** * Create an Edge. * * @param a Index of one endpoint of the edge * @param b Index of the other endpoint of the edge */ public Edge( int a, int b ) { p1=a; p2=b; p3=p4=-1; } /** * Add a triangle point to this edge. * * @param p triangle point to add */ public void add( int p ) { if( p3<0 ) p3=p; else p4=p; } } /** * Do it! * @throws Exception */ public void doit() throws Exception { sc = new Scanner( System.in ); //new File( "worm.in" ) ); ps = System.out; //new PrintStream( new FileOutputStream( "worm.out" ) ); // Pre-build structures Vertex vertices[] = new Vertex[MAX_VERTICES]; for( int i=0; i queue = new LinkedList(); // A list of all of the Faces we find. LinkedList faces = new LinkedList(); for(;;) { int n = sc.nextInt(); if( n==0 ) break; // Empty out the edges for( int i=0; i0.0 ) yz += Math.PI; // Now, find the other triangle point, by looking for the smallest // angle to the X axis int p4 = -1; mina = TWOPI; mind = Double.MAX_VALUE; boolean flipped = false; for( int i=0; i