CF135B Rectangle and Square

原题链接：B. Rectangle and Square

Tag：数学、模拟

题目描述

给定 \(8\) 个点，判断它们是否能组成一个正方形和一个矩形。 矩形可以是正方形，且长方形和正方形面积均非零。不强制要求图形和坐标轴平行。

分析

首先注意到题目只有 \(8\) 个点， 所以我们可以使用 \(O(8!)\) 的全排列方法的来做。

我们可以枚举所有的排列顺序，每次判断前四个点是否可以组成一个正方形，再判断后面四个点能否组成一个长方形。

现在问题变成了如何判断四个点能否组成正方形和长方形。 这里存在一个 naive 的想法是我们对于前四个点判断 \((0,1),(1,2),(2,3),(3,0)\) 这些点的距离是否相等， 对于后四个点判断是否存在两组相等的即可。

但是这样并不充分，因为可能出现图形是菱形和平行四边形的情况， 因此我们需要确保每一个图形中存在一个直角，这个可以用勾股定理来解决。

我的代码实现的比较烂，写了 \(\text{tuple<int,int,int>}\) 最后 \(\text{get}\) 取值的时候可能不太美观， 换成 \(\text{array}\) 来实现或许更加美观。

代码实现

void NeverSayNever() {
    vector<tuple<int, int, int>> vec(8);
    for (int i = 0; i < 8; ++i) {
        auto &[x, y, id] = vec[i];
        cin >> x >> y;
        id = i + 1;
    }
    std::sort(vec.begin(), vec.end());
    auto calc = [&](int i, int j) {
        auto [x1, y1, id1] = vec[i];
        auto [x2, y2, id2] = vec[j];
        return abs(x1 - x2) * abs(x1 - x2) + abs(y1 - y2) * abs(y1 - y2);
    };
    do {
        int tmp = calc(0, 1);
        if (tmp != 0 && tmp == calc(1, 2) && tmp == calc(2, 3) && tmp == calc(3, 0)
            && calc(0, 2) == tmp + calc(1, 2)) {
            if (calc(4, 5) == calc(6, 7) && calc(5, 6) == calc(4, 7)
                && calc(4, 5) != 0 && calc(5, 6) != 0 && calc(4, 6) == calc(4, 5) + calc(5, 6)) {
                cout << "YES" << endl;
                cout << get<2>(vec[0]) << " "
                     << get<2>(vec[1]) << " "
                     << get<2>(vec[2]) << " "
                     << get<2>(vec[3]) << " " << endl;
                cout << get<2>(vec[4]) << " "
                     << get<2>(vec[5]) << " "
                     << get<2>(vec[6]) << " "
                     << get<2>(vec[7]) << " " << endl;
                return;
            }
        }
    } while (std::next_permutation(vec.begin(), vec.end()));
    cout << "NO" << endl;
}

日志

本页面创建于 2025/6/19 00:22