#!/usr/bin/env python3 # # Based on polylabel by Mapbox (ISC License). # https://github.com/mapbox/polylabel # # Copyright (c) 2016, Mapbox # Permission to use, copy, modify, and/or distribute this software for any # purpose with or without fee is hereby granted, provided that the above # copyright notice and this permission notice appear in all copies. # # THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES # WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF # MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR # ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES # WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN # ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF # OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. from heapq import heappush, heappop # basically a quadtree SQRT2 = 2 ** .5 class Cell: def __init__(self, x, y, h, poly): self.x = x self.y = y self.h = h self.distance = polygon_distance(x, y, poly) self.max = self.distance + self.h * SQRT2 def __lt__(self, other): return self.max > other.max def polygon_distance(x, y, poly): inside = False minimum = float('inf') size = len(poly) for i in range(size): a, b = poly[i], poly[(i-1)%size] if (a[1] > y) != (b[1] > y) and x < (b[0] - a[0]) * (y - a[1]) / (b[1] - a[1]) + a[0]: inside = not inside minimum = min(minimum, segment_distance(x, y, a, b)) sqrt = minimum**.5 return 0 if minimum == 0 else sqrt if inside else -sqrt def segment_distance(px, py, a, b): x, y = a dx = b[0] - x dy = b[1] - y if dx != 0 or dy != 0: t = ((px - x) * dx + (py - y) * dy) / (dx * dx + dy * dy) if t > 1: x, y = b elif t > 0: x += dx*t y += dy*t dx = px-x dy = py-y return dx*dx + dy*dy ### inputs v, n = map(int, input().split()) poly = [list(map(int, input().split())) for _ in range(n)] ### ### find bounding box minx = miny = float('inf') maxx = maxy = float('-inf') for vert in poly: x, y = vert minx = min(minx, x) maxx = max(maxx, x) miny = min(miny, y) maxy = max(maxy, y) width = maxx-minx height = maxy-miny ### precision = 4e-7 q = [] best = Cell(minx + width/2, miny + height/2, 0, poly) def try_queue(x, y, h, best): cell = Cell(x, y, h, poly) if cell.max > best.distance + precision: heappush(q, cell) if cell.distance > best.distance: best = cell return best h = min(width, height)/2 x = minx while x < maxx: y = miny while y < maxy: best = try_queue(x + h, y + h, h, best) y += 2*h x += 2*h while q: current = heappop(q) if current.max - best.distance <= precision or current.h < precision: break h = current.h / 2 best = try_queue(current.x - h, current.y - h, h, best) best = try_queue(current.x + h, current.y - h, h, best) best = try_queue(current.x - h, current.y + h, h, best) best = try_queue(current.x + h, current.y + h, h, best) print(f"{best.distance / v:.9g}\n{best.x:.9g} {best.y:.9g}")