《J. 最大缘》题解

本题为 2025牛客寒假算法基础集训营2 废题，原题目名称为《一起画最大的圆！》，预估难度 2000 分。至此，真相大白！

让我们尝试用最标准的办法解决这道问题。

步骤一：子问题转换
$\hspace{15pt}$ 不妨设答案的三个点为 $(x_A,y_A)$ 、 $(x_B,y_B)$ 和 $(x_C,y_C)$ ，那么，最小的完全包含这三个点的矩形，一定是给定矩形区域的一个子矩形，也即我们将原问题转化为以下子问题：
现在，他已经划定了一个矩形区域，左侧边界为 $x=\min\{x_A,x_B,x_C\}$ ，右侧边界为 $x=\max\{x_A,x_B,x_C\}$ ，下侧边界为 $y=\min\{y_A,y_B,y_C\}$ ，上侧边界为 $y=\max\{y_A,y_B,y_C\}$ 。且满足 $\max\{x_A,x_B,x_C\}-\min\{x_A,x_B,x_C\} \le b - a$ 、 $\max\{y_A,y_B,y_C\}-\min\{y_A,y_B,y_C\} \le d - c$ 。
$\hspace{15pt}$ 显然，将答案的三点全体平移、左右对称、上下对称，子矩形也会同步发生位置上的变化，但其形状永不改变，且恒为给定矩形区域的子矩形。
步骤二：理论暴力解
$\hspace{15pt}$ 我们可以证明，仅通过上述这三个位置上的变动，一定存在一种方案，使得答案的其中一点恰好位于 $(a,d)$ 。我们将以此为突破口解决本题：固定第一点为 $(a,d)$ ， $\mathcal O(n^2)$ 暴力枚举第二个点，再 $\mathcal O(n^2)$ 暴力枚举第三个点，随后计算绘制圆的半径，找到最大的一个构造方案。这样做的时间复杂度为 $\mathcal O(n^4)$ ，理论上勉强可以通过，但是，由于求圆半径的函数常数较大，实际上是严格超时的。
步骤三：复杂度优化
$\hspace{15pt}$ 我们知道，当三点共线时，可以看作是画出了一个半径为无穷大的圆（可以使用正弦定理 $R=\dfrac{A}{\sin a}=\dfrac{B}{\sin b}=\dfrac{C}{\sin c}$ 证明）所以，当给定的三个点越接近共线，绘制出的圆也就越大。
$\hspace{15pt}$ 回到此前暴力的解法上，容易发现，在两个点确定直线的前提下，第三个点越贴近直线，构造出的方案越接近三点共线。记已经绘制出的直线方程为 $y=kx+b$ ，由于第三点一定位于整数坐标，所以，枚举 $x_0\in \{a \le x \le b \mid x \in \Bbb Z\}$ ，求解直线交每一列的点 $(x_0,kx_0+b)$ ，那么只需要检查这个点上下的整数点 $(x_0,\left\lceil{kx_0+b}\right\rceil)$ 和 $(x_0,\left\lfloor{kx_0+b}\right\rfloor)$ 即可；同理，枚举并检查 $y_0\in \{c \le y \le d \mid y \in \Bbb Z\}$ 后检查直线交每一行点的左右整数点。这样一来，我们可以将暴力枚举第三个点的复杂度优化到 $\mathcal O(n)$ 。
$\hspace{15pt}$ 最终复杂度为 $\mathcal O(n^3)$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
#ifdef WIDA_WORK_SPACE
    #include "debug.h"
#endif

using i64 = long long;
using f64 = long double;
f64 getCircleRadius(i64 x1, i64 y1, i64 x2, i64 y2, i64 x3, i64 y3) {
    i64 e = 2 * (x2 - x1);
    i64 f = 2 * (y2 - y1);
    i64 g = x2 * x2 - x1 * x1 + y2 * y2 - y1 * y1;

    i64 a = 2 * (x3 - x2);
    i64 b = 2 * (y3 - y2);
    i64 c = x3 * x3 - x2 * x2 + y3 * y3 - y2 * y2;

    if (e * b - a * f == 0) return 0;

    f64 X = 1.L * (g * b - c * f) / (e * b - a * f);
    f64 Y = 1.L * (a * g - c * e) / (a * f - b * e);
    f64 R2 = (X - x1) * (X - x1) + (Y - y1) * (Y - y1);
    return R2;
}

signed main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;

    f64 MaxR = 0;
    array<int, 6> ans;
    for (int i = a + 1; i <= b; i++) { // 注意从 +1 开始，因为共线时找不到第三个点
        for (int j = c + 1; j <= d; j++) {
            for (int x = a; x <= i; x++) { // 【对拍点其一】除2优化
                int y = c + (j - c) * (x - a) / (i - a);
                auto check = [&](int x, int y) {
                    f64 chk = getCircleRadius(a, c, i, j, x, y);
                    if (chk > MaxR) {
                        MaxR = chk;
                        ans = {a, c, i, j, x, y};
                    }
                };
                check(x, y);
                check(x, min(j, y + 1));
                check(x, max(c, y - 1));
            }
        }
    }

    for (int i = 0; i < 6; i++) {
        cout << ans[i] << " \n"[i % 2];
    }
}

int __OI_INIT__ = []() {
    ios::sync_with_stdio(0), cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(12);
    return 0;
}();

$\hspace{15pt}$ 本题还有一些与众不同的解法，比如，固定一点为左上角，随后在右下角 $25$ 个点中枚举，同时第三点使用与上方相同的办法枚举最贴近连出的直线的点，可以将复杂度优化到 $\mathcal O(25 \times n)$ ，经本人三天两夜数据全枚举，可以通过本题。可以说在当前的数据范围内这也是正解。顺带一提，如果范围是 $±100$ ，只需要枚举 $16$ 个点。

$\hspace{15pt}$ 另外还看到 KUN 哥的神秘 32ms 做法，没研究明白，先留个链接（留待读者自证）。

《K. 26》题解

$\hspace{15pt}$ 要求的内容为标准键盘 $26$ 键的相邻字母，打表输出即可（这就是为什么题目里有“默默敲键盘”）。

参考代码

#include <bits/stdc++.h>
using namespace std;
#ifdef WIDA_WORK_SPACE
    #include "debug.h"
#endif

using i64 = long long;

signed main() {
    char x;
    cin >> x;
    x -= 'A';

    vector<string> adj = {
        "QWSZ",
        "VGHN",
        "XDFV",
        "ERSFXC",
        "WRSD",
        "RTDGCV",
        "TYFHVB",
        "YUGJBN",
        "UOJK",
        "UIHKNM",
        "IOJLM",
        "OPK",
        "JKN",
        "HJBM",
        "IPKL",
        "OL",
        "WA",
        "ETDF",
        "WEADZX",
        "RYFG",
        "YIHJ",
        "FGCB",
        "QEAS",
        "SDZC",
        "TUGH",
        "ASX",
    };
    
    cout << adj[x] << "\n";
}
int __OI_INIT__ = []() {
    ios::sync_with_stdio(0), cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(12);
    return 0;
}();

JK 官解

《J. 最大缘》题解

《K. 26》题解