#include #include #include #include #include #include #include #include #include // STRATEGY: // Use the parametric form to sample many points along the boundary of the // ellipse, tracking the max/min coordinates of those points. // // Should this pass? I believe it is asymptotically worse than the binary search // (and of course the analytical solution). But I'm assuming this should pass. struct Point2d { double x, y; }; double distance(Point2d a, Point2d b) { double x = a.x - b.x; double y = a.y - b.y; return std::sqrt(x * x + y * y); } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); // input double a2; Point2d f1, f2; std::cin >> f1.x >> f1.y >> f2.x >> f2.y >> a2; // ellipse math double a = a2 / 2.; double c = distance(f1, f2) / 2; double b = std::sqrt(a * a - c * c); // flat ellipse has b = 0, should be okay Point2d center = {(f1.x + f2.x) / 2., (f1.y + f2.y) / 2.}; // rotated frame // NOTE: signs don't matter here for correctness below, they're probably wrong Point2d ax_X = {f1.x - center.x, f1.y - center.y}; double ax_Xnorm = std::sqrt(ax_X.x * ax_X.x + ax_X.y * ax_X.y); if (ax_Xnorm > 1e-10) { // numerics matter for degenerate case of a circle ax_X.x /= ax_Xnorm; ax_X.y /= ax_Xnorm; } else { ax_X = {1., 0.}; } Point2d ax_Y = {ax_X.y, -ax_X.x}; // Brute force search of points along the perminter double x_min = 777777; double x_max = -777777; double y_min = 777777; double y_max = -777777; double inc_rads = 1e-5; for (double theta = 0; theta < 2 * 3.15; theta += inc_rads) { // in reference frame Point2d ref = {a * std::cos(theta), b * std::sin(theta)}; // rotate in to frame Point2d rot = {ref.x * ax_X.x + ref.y * ax_Y.x, ref.x * ax_X.y + ref.y * ax_Y.y}; // translate into frame Point2d p = {rot.x + center.x, rot.y + center.y}; x_min = std::min(x_min, p.x); x_max = std::max(x_max, p.x); y_min = std::min(y_min, p.y); y_max = std::max(y_max, p.y); } std::cout << x_min << " " << y_min << " " << x_max << " " << y_max << std::endl; return 0; }