import java.awt.geom.Point2D; import java.io.BufferedOutputStream; import java.io.File; import java.io.FileOutputStream; import java.io.IOException; import java.io.PrintWriter; import java.util.Arrays; import java.util.Random; /** * */ /** * @author zeil * */ public class slotsGenerator { /** * A straight line in the 2-D plane. * * @author zeil * */ private static class Line { // ax + by + c = 0 private double a; private double b; private double c; /** * Create a line described by the equation ax + by + c = 0. * Note that the line ax + by + c = 0 is considered to be * the same line as (equal to) the line tax + tby + tc = 0 for * all positive t. * * @param a The coefficient of the x term * @param b The coefficient of the y term * @param c The constant term */ public Line (double a, double b, double c) { double r = Math.sqrt(a*a + b*b); this.a = a / r; this.b = b / r; this.c = c /r; } /** * Create a line passing through two points. * @param p1 a point that the line passes through * @param p2 another point that the line passes through * * @precondition: !p1.equals(p2) */ public Line (Point2D.Double p1, Point2D.Double p2) { double dx = p2.x - p1.x; double dy = p2.y - p1.y; a = dy; b = -dx; c = p1.y * dx - p1.x * dy; double r = Math.sqrt(a*a + b*b); a /= r; b /= r; c /= r; } /** * Create a string describing this line in the form "ax + by + c = 0" * where "a", "b", and "c" are replaced by appropriate floating point * values. * * @return string representation of this line. */ public String toString() { return "" + a + "x + " + b + "y + " + c + "= 0"; } /** * Compute the orthogonal distance of a point from this line (i.e., the * distance between that point and the closest point lying on this line). * * The distance value should indicate the direction of the point by its * sign. Points above and to the right of the lien should have a positive * distance. Points below and to the left should have a negative distance. * * @param p A point * @return signed distance of that point form this line */ double distance (Point2D.Double p) { return a * p.x + b * p.y + c; } public boolean equals(Object obj) { if (obj instanceof Line) { Line line2 = (Line)obj; return line2.a == a && line2.b == b && line2.c == c; } else return false; } } public slotsGenerator() { } private static void generate(int N, String fileNameBase) throws IOException { N = Math.max(3, N); N = Math.min(20, N); Random rand = new Random(); double xc = 10.0 + 80.0 * rand.nextDouble(); double yc = 10.0 + 80.0 * rand.nextDouble(); double r = 10 + 40.0 * rand.nextDouble(); r = Math.min(r, xc); r = Math.min(r, yc); r = Math.min(r, 100.0 - xc); r = Math.min(r, 100.0 - yc); double[] angles = new double[N]; for (int i = 0; i < N; ++i) { angles[i] = 2.0 * Math.PI * rand.nextDouble(); } Arrays.sort(angles); Point2D.Double[] vertices = new Point2D.Double[N]; for (int i = 0; i < N; ++i) { double x = r * Math.cos(angles[i]) + xc; double y = -r * Math.sin(angles[i]) + yc; vertices[i] = new Point2D.Double(x,y); } File inFile = new File(fileNameBase + ".in"); PrintWriter fout = new PrintWriter(new BufferedOutputStream(new FileOutputStream(inFile))); fout.println(N); for (Point2D.Double p: vertices) { fout.printf("%.2f %.2f\n", p.getX(), p.getY()); } fout.close(); File ansFile = new File(fileNameBase + ".ans"); fout = new PrintWriter(new BufferedOutputStream(new FileOutputStream(ansFile))); double minSlot = Double.MAX_VALUE; for (int i = 0; i < N; ++i) { Line side = new Line(vertices[i], vertices[(i + 1) % N]); double maxDist = 0.0; for (int j = 2; j < N; ++j) { Point2D.Double p = vertices[(i + j) % N]; double d = Math.abs(side.distance(p)); maxDist = Math.max(maxDist, d); } minSlot = Math.min(minSlot, maxDist); } fout.printf("%.2f\n", minSlot); fout.close(); } /** * Usage: * java slotsGenerator N fileName * places a random polygon with N vertices into fileName.in and * fileName.ans. * * @param args * @throws IOException */ public static void main (String[] argv) throws IOException { int n = Integer.parseInt(argv[0]); generate (n, argv[1]); } }