2025牛客寒假算法基础集训营第 2 场补题

H-一起画很大的圆

H-一起画很大的圆

题意

给定一个矩形区域，在矩形的边界上找到 3 个整数点，使得过这 3 个点画出的圆面积最大，输出这三个点的坐标。

思路

三个不共线的点确定一个圆。

如果这三个点越接近一条直线，这个圆最大。

要使得圆尽可能大，那么这三个点尽量趋近于在一条直线上，就是三个点连成的角尽可能大，越接近 180° 越优。

1. 横着的矩形

• (a,d-1), (b-1,d), (b,d)，其他的方位也行

2. 竖着的矩形

• (a,c), (a,c+1), (a+1,d)，其他的方位也行

//      https://ac.nowcoder.com/acm/contest/95334/H
//      三点依次连线，越趋近于一条直线，所在圆的半径就越大
//      就是说三点构成的角度越接近180°，答案越优，就是钝角
//      1：横着的矩形
//      (a,d-1), (b-1,d), (b,d)，其他的方位也行
//      2：竖着的矩形
//      (a,c), (a,c+1), (a+1,d)，其他的方位也行

#include <bits/stdc++.h>
using namespace std;
// #define int long long

int t, n, m;
void solve()
{
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    int x = b - a, y = d - c;
    if (x >= y)
    {
        cout << a << " " << d - 1 << "\n";
        cout << b - 1 << " " << d << "\n";
        cout << b << " " << d << "\n";
    }
    else
    {
        cout << a << " " << c << "\n";
        cout << a << " " << c + 1 << "\n";
        cout << a + 1 << " " << d << "\n";
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}