// O(n^2) solution to stars (intended) import java.util.*; import java.io.*; public class stars_font { public static void main(String[] args) throws Exception { PrintWriter out = new PrintWriter(System.out); new stars_font(new FastScanner(System.in), out); out.close(); } // Fix out random number generator (for determinism in debugging). Random random = new Random(1337); // Projection [0, 1.0] double scaleProj(vec3 dv, vec3 p) { return dv.dot(p) / dv.mag2(); } // Projection [0, len(dv)] double scaleProjK(vec3 dv, vec3 p) { return dv.dot(p) / dv.mag(); } // Project the given vector onto the line (0,0,0) -> dv vec3 proj(vec3 dv, vec3 p) { return dv.scale(scaleProj(dv, p)); } int N; vec3[] pts; // Project all points on this line and calculate the height of this vector double calcHeight(vec3 dv) { double lowest = Long.MAX_VALUE; double highest = Long.MIN_VALUE; for (vec3 p : pts) { double s = scaleProjK(dv, p); lowest = Math.min(lowest, s); highest = Math.max(highest, s); } return highest-lowest; } // Project all points onto the plane. Calculate bounding circle. double calcRadius(vec3 dv) { // Construct an orthogonal basis for this vector. vec3 uv1 = new vec3(-dv.y, -dv.z, dv.x); if (uv1.eq(dv)) uv1 = new vec3(dv.y, -dv.z, -dv.x); vec3 axis1 = dv.cross(uv1); vec3 axis2 = dv.cross(axis1); double halfPi = Math.PI/2; if (!GEOM.eq(halfPi, dv.angleBtwn(axis1)) || !GEOM.eq(halfPi, dv.angleBtwn(axis2)) || !GEOM.eq(halfPi, axis1.angleBtwn(axis2))) { System.out.println("Error: Orthogonal basis not found."); } vec2[] vs = new vec2[N]; for (int i=0; i faces = new ArrayDeque<>(); ArrayDeque pending = new ArrayDeque<>(); faces.add(new Face(0,1,2)); faces.add(new Face(0,2,1)); for (int p=3; p0) { Face f = faces.poll(); vec3 dv = v.sub(vs[f.spin[0]]); double dt = dv.dot(f.norm); if (dt > GEOM.EPS) { int i = f.spin[0]; int j = f.spin[1]; int k = f.spin[2]; edge[i][j]--; edge[j][k]--; edge[k][i]--; } else { faces.add(f); } } // Expand the faces using the new point for (Face f : faces) { for (int c=0; c<3; c++) { int i = f.spin[(c+1)%3]; int j = f.spin[c]; if (edge[i][j] == 0) pending.add(new Face(i, j, p)); } } faces.addAll(pending); pending.clear(); } vec3[] norms = new vec3[faces.size()]; int ptr = 0; for (Face f : faces) norms[ptr++] = f.norm; return norms; } class Face { int[] spin; vec3 norm; Face(int i, int j, int k) { norm = vs[j].sub(vs[i]).cross(vs[k].sub(vs[i])); spin = new int[]{i,j,k}; edge[i][j]++; edge[j][k]++; edge[k][i]++; } public String toString() { return String.format("%d %d %d", spin[0], spin[1], spin[2]); } } } class vec3 { double x, y, z; vec3(double xx, double yy, double zz) { x=xx; y=yy; z=zz; } boolean eq(vec3 rhs) { return GEOM.eq(x, rhs.x) && GEOM.eq(y, rhs.y) && GEOM.eq(z, rhs.z); } vec3 add(vec3 rhs) { return new vec3(x+rhs.x, y+rhs.y, z+rhs.z); } vec3 sub(vec3 rhs) { return new vec3(x-rhs.x, y-rhs.y, z-rhs.z); } vec3 scale(double s) { return new vec3(x*s, y*s, z*s); } double dot(vec3 rhs) { return x*rhs.x + y*rhs.y + z*rhs.z; } vec3 cross(vec3 rhs) { double xn = y*rhs.z-z*rhs.y; double yn = z*rhs.x-x*rhs.z; double zn = x*rhs.y-y*rhs.x; return new vec3(xn, yn, zn); } double mag() { return Math.sqrt(mag2()); } double mag2() { return x*x+y*y+z*z; } double angleBtwn(vec3 rhs) { double mag1 = mag(), mag2 = rhs.mag(); if (mag1 < GEOM.EPS || mag2 < GEOM.EPS) return 0.0; double dt = dot(rhs); return Math.acos(dt/(mag1*mag2)); } public String toString() { return String.format("%.6f %.6f %.6f", x, y, z); } } // http://www.cs.uu.nl/docs/vakken/ga/slides4b.pdf class CircleSearch { int N; vec2[] pts; // Assumes that the points are given in random order CircleSearch(vec2[] pts) { N = pts.length; this.pts = new vec2[N]; for (int i=0; i 0 && (left == null || pq.cross(c.cen.sub(p)) > pq.cross(left.cen.sub(p)))) { left = c; } else if (cx < 0 && (right == null || pq.cross(c.cen.sub(p)) < pq.cross(right.cen.sub(p)))) { right = c; } } if (left == null && right == null) return circ; else if (left == null) return right; else if (right == null) return left; else return left.rad <= right.rad ? left : right; } circle2 makeDiameter(vec2 a, vec2 b) { vec2 m = a.midpoint(b); return new circle2(m, a.dist(m)); } circle2 makeCircumcircle(vec2 a, vec2 b, vec2 c) { vec2 p = circle2.getCenter(a, b, c); if (p == null) return null; return new circle2(p, p.dist(a)); } } class circle2 { vec2 cen; double rad; circle2(vec2 c, double r) { cen = c; rad = r; } boolean onBorder(vec2 p) { return GEOM.eq(cen.dist(p), rad); } boolean contains(vec2 p) { return cen.dist(p) <= rad+GEOM.EPS; } static vec2 getCenter(vec2 p1, vec2 p2, vec2 p3) { vec2 m1 = p1.midpoint(p2); vec2 m2 = p3.midpoint(p2); vec2 n1 = new vec2(p2.y - p1.y, p1.x - p2.x); vec2 n2 = new vec2(p2.y - p3.y, p3.x - p2.x); if (GEOM.eq(n1.cross(n2), 0)) return null; line2 L1 = new line2(m1, m1.add(n1)); line2 L2 = new line2(m2, m2.add(n2)); return L1.intersect(L2); } public String toString() { return String.format("(%s, %.6f)", cen, rad); } } class line2 { vec2 e1, e2; line2(vec2 a, vec2 b) { e1=a; e2=b; } vec2 getVec2() { return e2.sub(e1); } vec2 intersect(line2 rhs) { vec2 v1 = getVec2(), v2 = rhs.getVec2(), v3 = rhs.e1.sub(e1); double div = v1.cross(v2), sn = v3.cross(v2); double s = sn/div; return v1.scale(s).add(e1); } } class vec2 implements Comparable { double x, y; vec2(double xx, double yy) { x=xx; y=yy; } boolean eq(vec2 rhs) { return GEOM.eq(x,rhs.x) && GEOM.eq(y,rhs.y); } public int compareTo(vec2 rhs) { if (GEOM.eq(x, rhs.x)) { if (GEOM.eq(y, rhs.y)) return 0; return Double.compare(y, rhs.y); } return Double.compare(x, rhs.x); } vec2 add(vec2 rhs) { return new vec2(x+rhs.x, y+rhs.y); } vec2 sub(vec2 rhs) { return new vec2(x-rhs.x, y-rhs.y); } vec2 scale(double s) { return new vec2(s*x, s*y); } double dot(vec2 rhs) { return x*rhs.x + y*rhs.y; } double cross(vec2 rhs) { return x*rhs.y - y*rhs.x; } vec2 midpoint(vec2 rhs) { return new vec2(0.5 * (x+rhs.x), 0.5 * (y+rhs.y)); } double mag2() { return x*x+y*y; } double mag() { return Math.sqrt(mag2()); } double dist(vec2 rhs) { return sub(rhs).mag(); } vec2 orthoCW() { return new vec2(y, -x); } vec2 orthoCCW() { return new vec2(-y, x); } public String toString() { return String.format("<%.7f, %.7f>", x, y); } } class GEOM { static double EPS = 1e-9; static boolean eq(double a, double b) { double d = Math.abs(a-b); if (d < EPS) return true; return d < EPS * Math.max(Math.abs(a), Math.abs(b)); } } class FastScanner{ private InputStream stream; private byte[] buf = new byte[1024]; private int curChar; private int numChars; public FastScanner(InputStream stream) { this.stream = stream; } int read() { if (numChars == -1) throw new InputMismatchException(); if (curChar >= numChars){ curChar = 0; try{ numChars = stream.read(buf); } catch (IOException e) { throw new InputMismatchException(); } if (numChars <= 0) return -1; } return buf[curChar++]; } boolean isSpaceChar(int c) { return c==' '||c=='\n'||c=='\r'||c=='\t'||c==-1; } boolean isEndline(int c) { return c=='\n'||c=='\r'||c==-1; } int nextInt() { return Integer.parseInt(next()); } long nextLong() { return Long.parseLong(next()); } double nextDouble() { return Double.parseDouble(next()); } String next(){ int c = read(); while (isSpaceChar(c)) c = read(); StringBuilder res = new StringBuilder(); do{ res.appendCodePoint(c); c = read(); }while(!isSpaceChar(c)); return res.toString(); } String nextLine(){ int c = read(); while (isEndline(c)) c = read(); StringBuilder res = new StringBuilder(); do{ res.appendCodePoint(c); c = read(); }while(!isEndline(c)); return res.toString(); } }