#include #include #include #include #include #include /** This is a classic computational geometry problem that can be solved elegantly by combining binary search with a half-plane intersection algorithm. Here is a C++ solution and a detailed explanation of the method. Method Explanation The problem asks for the time it takes for a fire, lit simultaneously on all edges of a forest polygon, to burn the entire area. The fire spreads inwards at a constant speed v. Geometric Interpretation: The time it takes for the fire to reach any point P inside the forest is determined by the shortest distance from P to the forest boundary (any of its edges), divided by the fire's speed v. The entire forest is burnt when the fire reaches the point(s) that are farthest from the boundary. The Farthest Point: This "last point to burn" is the center of the largest possible circle that can be inscribed within the forest polygon. The radius of this circle, let's call it d_max, is the maximum shortest-distance any interior point has to the boundary. Finding the Time and Location: The time to burn the whole forest is t = d_max / v. The location of the last point to burn is the center of this largest inscribed circle. Binary Search on the Answer: Directly calculating d_max is complex. Instead, we can binary search for its value. We can ask a simpler question: "Is it possible to fit a circle of a given radius r inside the polygon?" If a circle of radius r fits, it means there exists at least one point inside the forest that is r distance away from all edges. We can then try a larger radius. If it doesn't fit, r is too large, and we must try a smaller one. Checking a Radius r (The check function): For a circle of radius r to fit, its center must be at least r units away from every edge of the polygon. For each edge of the polygon, the set of points that are at least r distance away from it (on the "inward" side) forms a half-plane. If we find the intersection of all these n half-planes (one for each edge), we get a new, smaller convex polygon. Any point inside this new polygon is a valid center for an inscribed circle of radius r. Therefore, our check(r) function succeeds if this intersection of half-planes is non-empty. Half-Plane Intersection Algorithm: This is a standard algorithm in computational geometry used to find the common area (kernel) defined by a set of linear inequalities. We represent each half-plane as a directed line, where the valid region is to its left. The lines are sorted by their angle. A deque (double-ended queue) is used to maintain the lines that form the boundary of the current intersection area. As new lines are processed, redundant lines are removed from both the front and back of thedeque. If the final deque contains at least 3 lines, a valid intersection polygon exists. Final Solution: We binary search for the maximum possible r (d_max). The final r value gives the time (r/v). The check(r) function, when run with this final r, will produce a tiny polygon (possibly degenerated to a line or a point). Any vertex of this final polygon is a valid coordinate for the last point to be set alight. This approach assumes the input polygon is simple (doesn't intersect itself) and works for both convex and concave shapes. **/ // Using a small epsilon for floating-point comparisons const double EPS = 1e-9; // Structure to represent a point or a 2D vector struct Point { double x, y; }; // Vector arithmetic operators 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, double s) { return {a.x * s, a.y * s}; } Point operator/(Point a, double s) { return {a.x / s, a.y / s}; } // Vector operations double dot(Point a, Point b) { return a.x * b.x + a.y * b.y; } double cross(Point a, Point b) { return a.x * b.y - a.y * b.x; } double magnitude(Point a) { return sqrt(dot(a, a)); } Point normalize(Point a) { double mag = magnitude(a); if (mag < EPS) return {0, 0}; return a / mag; } // Structure to represent a line in point-vector form. // The valid half-plane is to the left of the vector v. struct Line { Point p, v; double angle; Line() {} Line(Point p, Point v) : p(p), v(v) { angle = atan2(v.y, v.x); } }; // Comparator for sorting lines by angle. // If angles are the same, the one further to the left is more restrictive. bool operator<(const Line& a, const Line& b) { if (fabs(a.angle - b.angle) < EPS) { return cross(a.v, b.p - a.p) < 0; } return a.angle < b.angle; } // Check if a point p is to the left of or on the line l bool on_left(const Line& l, const Point& p) { return cross(l.v, p - l.p) > -EPS; } // Compute the intersection point of two lines Point get_intersection(const Line& a, const Line& b) { Point u = a.p - b.p; double t = cross(b.v, u) / cross(a.v, b.v); return a.p + a.v * t; } // Computes the intersection of a set of half-planes, returning the vertices of the resulting convex polygon. std::vector half_plane_intersection(std::vector& lines) { std::sort(lines.begin(), lines.end()); // Remove parallel lines that are less restrictive lines.erase(std::unique(lines.begin(), lines.end(), [](const Line& a, const Line& b) { return fabs(a.angle - b.angle) < EPS; }), lines.end()); std::deque dq; for (const auto& line : lines) { while (dq.size() > 1 && !on_left(line, get_intersection(dq[dq.size()-2], dq.back()))) { dq.pop_back(); } while (dq.size() > 1 && !on_left(line, get_intersection(dq.front(), dq[1]))) { dq.pop_front(); } dq.push_back(line); } // Final cleanup: check front against back and vice-versa while (dq.size() > 2 && !on_left(dq.front(), get_intersection(dq[dq.size()-2], dq.back()))) { dq.pop_back(); } while (dq.size() > 2 && !on_left(dq.back(), get_intersection(dq.front(), dq[1]))) { dq.pop_front(); } // If less than 3 lines, the intersection is not a bounded polygon if (dq.size() < 3) { return {}; } // Compute the vertices of the intersection polygon std::vector result_poly; for (size_t i = 0; i < dq.size(); ++i) { result_poly.push_back(get_intersection(dq[i], dq[(i + 1) % dq.size()])); } return result_poly; } int n; double v; std::vector forest_poly; Point last_point; // To store the coordinates of the last point // Check if a circle of radius r can be inscribed in the polygon bool check(double r) { std::vector half_planes; for (int i = 0; i < n; ++i) { Point p1 = forest_poly[i]; Point p2 = forest_poly[(i + 1) % n]; Point edge_vec = p2 - p1; Point normal_vec = {-edge_vec.y, edge_vec.x}; // Inward normal for CCW polygon Point normalized_normal = normalize(normal_vec); // Shift the line inwards by r Point shifted_p = p1 + normalized_normal * r; half_planes.push_back(Line(shifted_p, edge_vec)); } std::vector intersection = half_plane_intersection(half_planes); if (!intersection.empty()) { // If an intersection exists, it's a valid configuration. // Store one of its vertices as a candidate for the last point. last_point = intersection[0]; return true; } return false; } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); std::cin >> v >> n; forest_poly.resize(n); for (int i = 0; i < n; ++i) { std::cin >> forest_poly[i].x >> forest_poly[i].y; } // Ensure polygon vertices are in Counter-Clockwise (CCW) order // by checking the signed area (shoelace formula). double area = 0.0; for (int i = 0; i < n; ++i) { area += cross(forest_poly[i], forest_poly[(i + 1) % n]); } if (area < 0) { std::reverse(forest_poly.begin(), forest_poly.end()); } double low = 0, high = 200000.0; // Binary search for the maximum radius for (int i = 0; i < 100; ++i) { // 100 iterations for required precision double mid = (low + high) / 2.0; if (check(mid)) { low = mid; // Radius mid is possible, try for a larger one } else { high = mid; // Radius mid is too large } } // Rerun check with the final radius to get the final point location check(low); double time = low / v; std::cout << std::fixed << std::setprecision(8) << time << std::endl; std::cout << std::fixed << std::setprecision(8) << last_point.x << " " << last_point.y << std::endl; return 0; }