#include #include #include #include #include #include #include // Use long double for higher precision using LD = long double; const LD EPS = 1e-9; const LD INF = 1e18; // --- Structures --- struct Point { LD x, y; // For sorting and using in std::set bool operator<(const Point& other) const { if (std::abs(x - other.x) > EPS) return x < other.x; return y < other.y - EPS; } bool operator==(const Point& other)const { return std::abs(x-other.x) EPS) { a /= norm; b /= norm; c /= norm; } } Line(LD A, LD B, LD C) : a(A), b(B), c(C) {} }; // Global polygon data int N; std::vector P; std::vector edge_lines; // --- Vector/Point Operations --- Point operator+(Point a, Point b) { return {a.x + b.x, a.y + b.y}; } Point operator-(Point a, Point b) { return {a.x - b.x, a.y - b.y}; } Point operator*(Point a, LD s) { return {a.x * s, a.y * s}; } Point operator/(Point a, LD s) { return {a.x / s, a.y / s}; } LD dot(Point a, Point b) { return a.x * b.x + a.y * b.y; } LD norm_sq(Point a) { return dot(a, a); } LD dist(Point a, Point b) { return sqrt(norm_sq(a - b)); } // --- Geometric Primitives --- // Solves ax^2 + bx + c = 0 int solve_quadratic(LD a, LD b, LD c, LD& r1, LD& r2) { if (std::abs(a) < EPS) { if (std::abs(b) < EPS) return 0; r1 = r2 = -c / b; return 1; } LD delta = b * b - 4 * a * c; if (delta < -EPS) return 0; if (delta < 0) delta = 0; LD sqrt_delta = sqrt(delta); r1 = (-b + sqrt_delta) / (2 * a); r2 = (-b - sqrt_delta) / (2 * a); return (std::abs(delta) < EPS) ? 1 : 2; } bool line_intersect(Line l1, Line l2, Point& out) { LD det = l1.a * l2.b - l2.a * l1.b; if (std::abs(det) < EPS) return false; out.x = (l1.b * l2.c - l2.b * l1.c) / det; out.y = (l2.a * l1.c - l1.a * l2.c) / det; return true; } LD dist_point_segment(Point p, Point a, Point b) { if (dot(p - a, b - a) < 0) return dist(p, a); if (dot(p - b, a - b) < 0) return dist(p, b); return std::abs(Line(a, b).a * p.x + Line(a, b).b * p.y + Line(a, b).c); } Point closest_point_on_segment(Point p, Point a, Point b) { if (dot(p - a, b - a) <= 0) return a; if (dot(p - b, a - b) <= 0) return b; LD t = dot(p - a, b - a) / norm_sq(b - a); return a + (b - a) * t; } LD dist_to_polygon(Point p) { LD min_dist = INF; for (int i = 0; i < N; ++i) { min_dist = std::min(min_dist, dist_point_segment(p, P[i], P[(i + 1) % N])); } return min_dist; } // Point-in-polygon test using the ray casting algorithm bool is_inside(Point p) { bool inside = false; for (int i = 0, j = N - 1; i < N; j = i++) { if (dist_point_segment(p, P[i], P[j]) < EPS) return true; // On boundary if (((P[i].y > p.y) != (P[j].y > p.y)) && (p.x < (P[j].x - P[i].x) * (p.y - P[i].y) / (P[j].y - P[i].y) + P[i].x)) { inside = !inside; } } return inside; } // --- Validation and Candidate Management --- void add_if_valid(Point candidate, std::set& solutions) { if (std::isinf(candidate.x) || std::isinf(candidate.y) || std::isnan(candidate.x) || std::isnan(candidate.y)) { return; } LD min_dist = dist_to_polygon(candidate); if (min_dist < EPS) return; std::vector closest_points; for (int i = 0; i < N; ++i) { Point p1 = P[i], p2 = P[(i + 1) % N]; Point closest = closest_point_on_segment(candidate, p1, p2); if (std::abs(dist(candidate, closest) - min_dist) < EPS) { closest_points.push_back(closest); } } // Deduplicate closest points std::sort(closest_points.begin(), closest_points.end()); closest_points.erase(std::unique(closest_points.begin(), closest_points.end()), closest_points.end()); if (closest_points.size() == 2 || closest_points.size() == 3) { solutions.insert(candidate); } } // --- Candidate Generation Functions --- void generate_vvv(std::set& solutions) { for (int i = 0; i < N; ++i) for (int j = i + 1; j < N; ++j) for (int k = j + 1; k < N; ++k) { Point p1 = P[i], p2 = P[j], p3 = P[k]; Point m1 = (p1 + p2) / 2.0, m2 = (p2 + p3) / 2.0; Point v1 = {p2.y - p1.y, p1.x - p2.x}; Point v2 = {p3.y - p2.y, p2.x - p3.x}; Line perp1(m1, m1 + v1), perp2(m2, m2 + v2); Point center; if (line_intersect(perp1, perp2, center)) add_if_valid(center, solutions); } } void generate_eee(std::set& solutions) { for (int i = 0; i < N; ++i) for (int j = i + 1; j < N; ++j) for (int k = j + 1; k < N; ++k) { Line l1 = edge_lines[i], l2 = edge_lines[j], l3 = edge_lines[k]; for (int s1 = -1; s1 <= 1; s1 += 2) for (int s2 = -1; s2 <= 1; s2 += 2) { Line b1 = {l1.a - s1 * l2.a, l1.b - s1 * l2.b, l1.c - s1 * l2.c}; Line b2 = {l2.a - s2 * l3.a, l2.b - s2 * l3.b, l2.c - s2 * l3.c}; Point center; if (line_intersect(b1, b2, center)) add_if_valid(center, solutions); } } } void solve_line_parabola(Line l, Point focus, Line directrix, std::set& solutions) { // Transform coordinates so directrix is x-axis (y=0) and focus is on y-axis (0, d) Point p_on_directrix = {-directrix.a * directrix.c, -directrix.b * directrix.c}; LD angle = atan2(directrix.b, -directrix.a); auto rotate = [&](Point p, LD a) { return Point{p.x*cos(a)-p.y*sin(a), p.x*sin(a)+p.y*cos(a)}; }; Point focus_tr = rotate(focus - p_on_directrix, angle); Line l_tr = {l.a*cos(angle)+l.b*sin(angle), -l.a*sin(angle)+l.b*cos(angle), l.a*p_on_directrix.x+l.b*p_on_directrix.y+l.c}; if (std::abs(focus_tr.y) < EPS) return; // Degenerate parabola // Parabola in transformed space: y = (x^2 - 2*x*focus_tr.x + norm_sq(focus_tr)) / (2*focus_tr.y) // Line in transformed space: l_tr.a*x + l_tr.b*y + l_tr.c = 0 LD qa, qb, qc; if (std::abs(l_tr.b) > EPS) { // y = mx+k form LD m = -l_tr.a / l_tr.b, k = -l_tr.c / l_tr.b; qa = 1.0; qb = -2 * focus_tr.x - 2 * focus_tr.y * m; qc = norm_sq(focus_tr) - 2 * focus_tr.y * k; } else { // x = k form LD k = -l_tr.c / l_tr.a; LD x = k; LD y = (x*x - 2*x*focus_tr.x + norm_sq(focus_tr)) / (2*focus_tr.y); Point cand_tr = {x, y}; Point cand_t = rotate(cand_tr, -angle); add_if_valid(cand_t + p_on_directrix, solutions); return; } LD r1, r2; int roots = solve_quadratic(qa, qb, qc, r1, r2); if (roots > 0) { LD x = r1, y = -l_tr.a / l_tr.b * x - l_tr.c / l_tr.b; Point cand_tr = {x, y}; Point cand_t = rotate(cand_tr, -angle); add_if_valid(cand_t + p_on_directrix, solutions); } if (roots > 1) { LD x = r2, y = -l_tr.a / l_tr.b * x - l_tr.c / l_tr.b; Point cand_tr = {x, y}; Point cand_t = rotate(cand_tr, -angle); add_if_valid(cand_t + p_on_directrix, solutions); } } void generate_vve(std::set& solutions) { for (int i = 0; i < N; ++i) { // Edge E Line E = edge_lines[i]; for (int j = 0; j < N; ++j) for (int k = j + 1; k < N; ++k) { // Vertices V1, V2 Point V1 = P[j], V2 = P[k]; // Perpendicular bisector of V1, V2 Point mid = (V1 + V2) / 2.0; Point dir = {V2.y - V1.y, V1.x - V2.x}; Line perp_bisector(mid, mid + dir); // Intersect bisector with parabola (focus V1, directrix E) solve_line_parabola(perp_bisector, V1, E, solutions); } } } void generate_vee(std::set& solutions) { for (int i = 0; i < N; ++i) { // Vertex V Point V = P[i]; for (int j = 0; j < N; ++j) for (int k = j + 1; k < N; ++k) { // Edges E1, E2 Line E1 = edge_lines[j], E2 = edge_lines[k]; // Angle bisectors of E1, E2 for (int s = -1; s <= 1; s += 2) { Line bisector = {E1.a - s * E2.a, E1.b - s * E2.b, E1.c - s * E2.c}; // Intersect bisector with parabola (focus V, directrix E1) solve_line_parabola(bisector, V, E1, solutions); } } } } void solve() { LD rate; std::cin >> rate >> N; P.resize(N); edge_lines.clear(); for (int i = 0; i < N; ++i) { std::cin >> P[i].x >> P[i].y; } for (int i = 0; i < N; ++i) { edge_lines.emplace_back(P[i], P[(i + 1) % N]); } std::set solutions; generate_vvv(solutions); generate_eee(solutions); generate_vve(solutions); generate_vee(solutions); Point best_point = {NAN, NAN}; LD max_dist = -1.0; bool found = false; for (const auto& p : solutions) { if (is_inside(p)) { LD d = dist_to_polygon(p); if (d > max_dist) { max_dist = d; best_point = p; found = true; } } } std::cout << std::fixed << std::setprecision(8); if (found) { std::cout << (double)max_dist / rate << std::endl; std::cout << (double)best_point.x << " " << (double)best_point.y << std::endl; } else { std::cout << "No internal medial axis vertex found." << std::endl; } } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); solve(); return 0; }