首先别用python太慢了

数学题：外接圆半径

首先外接圆半径可以用海伦公式计算。

double calculate_radius(int x1, int y1, int x2, int y2, int x3, int y3) {
    // 计算三条边的长度
    double a = sqrt((x2 - x3) * (x2 - x3) + (y2 - y3) * (y2 - y3));
    double b = sqrt((x1 - x3) * (x1 - x3) + (y1 - y3) * (y1 - y3));
    double c = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
    
    // 检查三角形是否合法
    if (a + b <= c || b + c <= a || a + c <= b) {
        return 0;
    }
    
    // 使用海伦公式计算面积
    double s = (a + b + c) / 2.0;
    double area = 0;
    // 注意：当面积接近0时可能会出现计算误差
    if (s * (s - a) * (s - b) * (s - c) < 1e-10) {
        return 0;
    }
    area = sqrt(s * (s - a) * (s - b) * (s - c));
    if (area < 1e-10) {
        return 0;
    }
    double radius = (a * b * c) / (4.0 * area);
    return radius;
}

最优解在什么情况取得？

学过曲率半径的都应该知道。 如果这三个点几乎成一条直线，那么半径肯定会非常大，那么就可以利用这个特性了。 固定A（a,b）为矩形左下角的点，变化点B（c,d）。然后可以通过这两点计算出一个直线的方程。然后以整数x遍历横坐标从a->c。对于每一个x计算直线对应的y然后向上取整（因为你只需要遍历尽可能接近直线的点，这样三个点才更像在一条直线上）那么就得到了第三个点c的坐标，计算这三点确定的外接圆半径，如果更大就试图更新最大值。一轮搜索后。B开始向A点移动，移动方式为B（a-1,c）,B（a,c-1）B(a-1,c-1)然后B（a-2,c）,B（a-2,c-1），B(a-2,c-2)，B（a-1,c-2），B（a,c-2）
然后可以了。这里其实还有优化的空间，因为如果点B后面移动时落在了之前遍历过的直线上那么这种情况可以直接舍弃。但是既然都AC了那就不管了

AC代码

// 思路是自己想的，代码是GPT写的
#include <iostream>
#include <cmath>
#include <limits>
#include <tuple>
using namespace std;

double calculate_radius(int x1, int y1, int x2, int y2, int x3, int y3) {
    // 计算三条边的长度
    double a = sqrt((x2 - x3) * (x2 - x3) + (y2 - y3) * (y2 - y3));
    double b = sqrt((x1 - x3) * (x1 - x3) + (y1 - y3) * (y1 - y3));
    double c = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
    
    // 检查三角形是否合法
    if (a + b <= c || b + c <= a || a + c <= b) {
        return 0;
    }
    
    // 使用海伦公式计算面积
    double s = (a + b + c) / 2.0;
    double area = 0;
    // 注意：当面积接近0时可能会出现计算误差
    if (s * (s - a) * (s - b) * (s - c) < 1e-10) {
        return 0;
    }
    area = sqrt(s * (s - a) * (s - b) * (s - c));
    if (area < 1e-10) {
        return 0;
    }
    double radius = (a * b * c) / (4.0 * area);
    return radius;
}

// 根据两点和 x 坐标计算第三个点的 y 坐标，返回是否计算成功
bool get_third_point(int x1, int y1, int x2, int y2, int x, int &yResult) {
    if (x2 == x1) {
        return false;
    }
    double k = double(y2 - y1) / double(x2 - x1);
    double b = y1 - k * x1;
    double y = k * x + b;
    yResult = int(ceil(y));
    return true;
}

tuple<int, int, int, int, int, int> find_max_radius_points(int a, int b, int c, int d) {
    double max_radius = 0;
    // 默认选择三点：(a,c), (a,d), (b,c)
    int bestAx = a, bestAy = c, bestBx = a, bestBy = d, bestCx = b, bestCy = c;
    
    // 固定A为左下角点
    int x1 = a, y1 = c;
    
    // 遍历B点的可能位置
    for (int x2 = a; x2 <= b; x2++) {
        for (int y2 = c; y2 <= d; y2++) {
            // 排除与A重合的情况
            if (x2 == x1 && y2 == y1) continue;
            
            // 对于每个可能的第三个点通过 x 坐标计算 y 坐标
            for (int x3 = a; x3 <= b; x3++) {
                // 排除与A或B重合的情况
                if (x3 == x1 || x3 == x2) continue;
                int y3;
                if (!get_third_point(x1, y1, x2, y2, x3, y3)) continue;
                if (y3 < c || y3 > d) continue;
                
                // 检查三点是否共线（利用向量叉乘判断）
                double cross = fabs((x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1));
                if (cross < 1e-10) continue;
                
                double r = calculate_radius(x1, y1, x2, y2, x3, y3);
                if (r > max_radius) {
                    max_radius = r;
                    bestAx = x1; bestAy = y1;
                    bestBx = x2; bestBy = y2;
                    bestCx = x3; bestCy = y3;
                }
            }
        }
    }
    return make_tuple(bestAx, bestAy, bestBx, bestBy, bestCx, bestCy);
}

int main() {
    int a, b, c, d;
    if(!(cin >> a >> b >> c >> d)) {
        cout << "输入格式错误" << endl;
        return 1;
    }
    
    if (a > b) swap(a, b);
    if (c > d) swap(c, d);
    
    if (!( (0 <= b - a && b - a <= 1000) && (0 <= d - c && d - c <= 1000) )) {
        cout << "输入范围应在1000以内" << endl;
        return 1;
    }
    
    auto points = find_max_radius_points(a, b, c, d);
    int ax, ay, bx, by, cx, cy;
    tie(ax, ay, bx, by, cx, cy) = points;
    
    cout << ax << " " << ay << "\n";
    cout << bx << " " << by << "\n";
    cout << cx << " " << cy << "\n";
    
    return 0;
}