#include #include #include #include #include #include /** Of course! You've correctly identified a subtle but crucial aspect of this problem. The point that's last to burn isn't just far from the polygon's edges, but from its vertices as well. My previous solution only accounted for the edges. A point P is safe at time t (with r = v*t) only if its distance to every part of the boundary (both edges and vertices) is at least r. This means P must be: Inside the polygon formed by shifting all edges inward by r. Outside of a circle of radius r centered at each vertex of the original polygon. The region of "safe" points can have holes in the middle, bounded by circular arcs. The vertices of these holes are formed by the intersection of two circles. Therefore, to ensure we find a safe point if one exists, we must check these circle-circle intersection points as candidate locations, in addition to the vertices of the shrunken polygon. I have updated the check function to implement this more robust logic. It now generates a list of candidate points (vertices of the shrunken polygon and all circle-circle intersection points) and tests if any of them satisfy both conditions. While this approach is more computationally intensive, it is guaranteed to be correct. Here is the modified C++ code: **/ // 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; } // New function for circle-circle intersection std::vector circle_circle_intersection(Point c1, double r1, Point c2, double r2) { Point d_vec = c2 - c1; double d_sq = dot(d_vec, d_vec); double d = sqrt(d_sq); if (d > r1 + r2 + EPS || d < fabs(r1 - r2) - EPS || d < EPS) { return {}; } double a = (d_sq + r1*r1 - r2*r2) / (2 * d); Point p_mid = c1 + (d_vec * (a / d)); double h_sq = r1*r1 - a*a; double h = sqrt(std::max(0.0, h_sq)); Point perp_vec = {-d_vec.y, d_vec.x}; Point p1 = p_mid + (perp_vec * (h / d)); Point p2 = p_mid - (perp_vec * (h / d)); if (h < EPS) return {p1}; return {p1, p2}; } int n; double v; std::vector forest_poly; Point last_point; // To store the coordinates of the last point // Check if a point exists that is at least r distance from all edges and vertices 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}; Point normalized_normal = normalize(normal_vec); Point shifted_p = p1 + normalized_normal * r; half_planes.push_back(Line(shifted_p, edge_vec)); } std::vector poly_r = half_plane_intersection(half_planes); if (poly_r.empty() && n > 0) { // n > 0 check to handle empty input case return false; } std::vector candidates = poly_r; for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { auto intersections = circle_circle_intersection(forest_poly[i], r, forest_poly[j], r); for (const auto& p : intersections) { candidates.push_back(p); } } } for (const auto& p : candidates) { bool is_in_poly = true; for (const auto& plane : half_planes) { if (!on_left(plane, p)) { is_in_poly = false; break; } } if (!is_in_poly) continue; bool is_outside_circles = true; for (int k = 0; k < n; ++k) { if (magnitude(p - forest_poly[k]) < r - EPS) { is_outside_circles = false; break; } } if (is_outside_circles) { last_point = p; 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; } 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; for (int i = 0; i < 100; ++i) { double mid = (low + high) / 2.0; if (check(mid)) { low = mid; } else { high = mid; } } 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; }