/** * Solution to Wild, Fire / Arboreal Challenge / forest * Author: Maxim Buzdalov * * Solution: * - binary search for the distance * - for the distance, find all intersection points between all: * - polygon segments offset by the distance * - circles extending from vertices * and check for each whether: * - it is inside the polygon * - the shortest distance between it and any polygon segment is at least the distance +- eps * Point found: return it, no point found: return null * * Complexity: O(n^3) times binary search */ import java.io.*; import java.util.*; public class forest_mb { static final double EPS = 1e-9; static final Point SOMEWHERE_OUTSIDE = new Point(-366, -239); static class Point { double x, y; Point(double x, double y) { this.x = x; this.y = y; } double dist2(Point that) { double dx = x - that.x; double dy = y - that.y; return dx * dx + dy * dy; } double vmul(Point a, Point b) { return (a.x - x) * (b.y - y) - (a.y - y) * (b.x - x); } double smul(Point a, Point b) { return (a.x - x) * (b.x - x) + (a.y - y) * (b.y - y); } public String toString() { return "(" + x + ", " + y + ")"; } } private static boolean distanceAtLeast(Point point, Point s1, Point s2, double distance) { // 1. If close enough to the endpoint, return false // eps handling is obviously not mathematically correct, but who cares? double d2 = distance * distance; if (point.dist2(s1) < d2 * (1 - EPS)) return false; if (point.dist2(s2) < d2 * (1 - EPS)) return false; // 2. Subject to being here, if the point projection is not inside of the segment, // aka some of the scalar products is non-positive, we are good. if (s1.smul(point, s2) < EPS || s2.smul(point, s1) < EPS) return true; // 3. Now we have to check the distance double vmul = point.vmul(s1, s2); return vmul * vmul / s1.dist2(s2) >= d2 * (1 - EPS); } private static boolean distanceAtLeast(Point point, Point[] poly, double distance) { int n = poly.length; Point prev = poly[n - 1]; for (int i = 0; i < n; ++i) { Point curr = poly[i]; if (!distanceAtLeast(point, prev, curr, distance)) return false; prev = curr; } return true; } private static int intersectSegments(Point p1, Point p2, Point q1, Point q2, Point[] dest) { // 1. If bounding boxes are far away, return false if (Math.max(p1.x, p2.x) < EPS + Math.min(q1.x, q2.x)) return 0; if (Math.max(p1.y, p2.y) < EPS + Math.min(q1.y, q2.y)) return 0; if (Math.max(q1.x, q2.x) < EPS + Math.min(p1.x, p2.x)) return 0; if (Math.max(q1.y, q2.y) < EPS + Math.min(p1.y, p2.y)) return 0; double a11 = p2.x - p1.x; double a12 = q1.x - q2.x; double a21 = p2.y - p1.y; double a22 = q1.y - q2.y; double b1 = q1.x - p1.x; double b2 = q1.y - p1.y; double det = a11 * a22 - a12 * a21; if (Math.abs(det) < EPS) { // In all cases where we have parallel segments, we may assume they do not intersect: // - In the inside test, we assume this does not happen because of fake general position // - In the offset segment intersections, collision of colinear segments will be done by // the circumference case return 0; } double t = (b1 * a22 - a12 * b2) / det; double u = (a11 * b2 - a21 * b1) / det; if (t < -EPS || t > 1 + EPS || u < -EPS || u > 1 + EPS) { return 0; } // Double-checking; remove when works double px = p1.x + t * (p2.x - p1.x); double py = p1.y + t * (p2.y - p1.y); double qx = q1.x + u * (q2.x - q1.x); double qy = q1.y + u * (q2.y - q1.y); if (dest != null) { dest[0].x = p1.x + t * (p2.x - p1.x); dest[0].y = p1.y + t * (p2.y - p1.y); } return 1; } private static int intersectCircles(Point p, Point q, double r, Point[] dest) { double r2 = r * r; double d2 = p.dist2(q) / 4; if (d2 > r2 + EPS) { return 0; } double cx = (p.x + q.x) / 2; double cy = (p.y + q.y) / 2; if (d2 > r2 - EPS) { dest[0].x = cx; dest[0].y = cy; return 1; } double scale = 0.5 * Math.sqrt(r2 / d2 - 1); double dx = (p.y - q.y) * scale; double dy = (q.x - p.x) * scale; dest[0].x = cx + dx; dest[0].y = cy + dy; dest[1].x = cx - dx; dest[1].y = cy - dy; return 2; } private static int intersectBoth(Point s1, Point s2, Point p, double r, Point[] dest) { // We may intersect with a line & it's OK, because we filter the points subsequently double a = s1.dist2(s2); double b = s1.smul(s2, p); double c = s1.dist2(p) - r * r; double d = b * b - a * c; if (Math.abs(d) < -EPS) { return 0; } if (d <= EPS) { double t = b / a; dest[0].x = s1.x + t * (s2.x - s1.x); dest[0].y = s1.y + t * (s2.y - s1.y); return 1; } else { d = Math.sqrt(d); double t0 = (b - d) / a; double t1 = (b + d) / a; dest[0].x = s1.x + t0 * (s2.x - s1.x); dest[0].y = s1.y + t0 * (s2.y - s1.y); dest[1].x = s1.x + t1 * (s2.x - s1.x); dest[1].y = s1.y + t1 * (s2.y - s1.y); return 2; } } private static boolean inside(Point point, Point[] poly) { int n = poly.length; // I am too lazy to write this in the classical side-tracking way // As `point` is generated by binary searches, // I assume setting a "random enough" external point as the other end would work Point prev = poly[n - 1]; boolean result = false; for (int i = 0; i < n; ++i) { Point curr = poly[i]; result ^= intersectSegments(point, SOMEWHERE_OUTSIDE, prev, curr, null) > 0; prev = curr; } return result; } private static Point findPoint(Point[] poly, double distance) { int n = poly.length; Point[] swap = new Point[] { new Point(0, 0), new Point(0, 0) }; // 1. Intersect circles first, because it is a bit cheaper for (int i1 = 0; i1 < n; ++i1) { for (int i2 = i1 + 1; i2 < n; ++i2) { int nPoints = intersectCircles(poly[i1], poly[i2], distance, swap); for (int t = 0; t < nPoints; ++t) { if (inside(swap[t], poly) && distanceAtLeast(swap[t], poly, distance)) { return swap[t]; } } } } // 2. Generate offset segments Point[] s1 = new Point[n]; Point[] s2 = new Point[n]; Point prev = poly[n - 1]; for (int i = 0; i < n; ++i) { Point curr = poly[i]; double scale = distance / Math.sqrt(prev.dist2(curr)); double dx = (prev.y - curr.y) * scale; double dy = (curr.x - prev.x) * scale; s1[i] = new Point(prev.x + dx, prev.y + dy); s2[i] = new Point(curr.x + dx, curr.y + dy); prev = curr; } // 2. For all pairs, run detectors for (int i1 = 0; i1 < n; ++i1) { for (int i2 = i1 + 1; i2 < n; ++i2) { for (int cs = 0; cs < 3; ++cs) { int nPoints = 0; switch (cs) { case 0: // intersect segments nPoints = intersectSegments(s1[i1], s2[i1], s1[i2], s2[i2], swap); break; case 1: // circle on left, segment on right nPoints = intersectBoth(s1[i1], s2[i1], poly[i2], distance, swap); break; case 2: // circle on right, segment on left nPoints = intersectBoth(s1[i2], s2[i2], poly[i1], distance, swap); break; } for (int t = 0; t < nPoints; ++t) { if (inside(swap[t], poly) && distanceAtLeast(swap[t], poly, distance)) { return swap[t]; } } } } } return null; } private static double orientedArea(Point[] poly) { int n = poly.length; Point prev = poly[n - 1]; double answer = 0; for (Point curr : poly) { answer -= curr.x * prev.y - curr.y * prev.x; prev = curr; } return answer; } public static void main(String[] args) throws IOException { try (Input in = new Input()) { int v = in.nextInt(); int n = in.nextInt(); Point[] poly = new Point[n]; for (int i = 0; i < n; ++i) { poly[i] = new Point(in.nextInt(), in.nextInt()); } if (orientedArea(poly) < 0) { Collections.reverse(Arrays.asList(poly)); } double distL = 0, distR = 2e5; Point best = null; for (int iter = 0; iter < 50; ++iter) { double distM = (distL + distR) / 2; Point pt = findPoint(poly, distM); if (pt == null) { distR = distM; } else { best = pt; distL = distM; } } System.out.println(distL / v); System.out.println(best.x + " " + best.y); } } private static class Input implements Closeable { private final BufferedReader in; private StringTokenizer st; Input() throws IOException { in = new BufferedReader(new InputStreamReader(System.in)); st = new StringTokenizer(in.readLine()); } int nextInt() throws IOException { while (!st.hasMoreTokens()) { st = new StringTokenizer(in.readLine()); } return Integer.parseInt(st.nextToken()); } public void close() throws IOException { in.close(); } } }