CSP-J 2021 第一轮 第 43 题：矩形计数：⑤处应填

题目

（ 2 ） （矩形计数） 平面上有 $n$ 个关键点，求有多少个四条边都和 $x$ 轴或者 $y$ 轴平行的矩形，满足四个顶点都是关键点。给出的关键点可能有重复，但完全重合的矩形只计一 次。

试补全枚举算法。

#include <iostream>
using namespace std;

struct point {
    int x, y, id;
};

bool equals(point a, point b) {
    return a.x == b.x && a.y == b.y;
}

bool cmp(point a, point b) {
    return ①;
}

void sort(point A[], int n) {
    for (int i = 0; i < n; i++)
        for (int j = 1; j < n; j++)
            if (cmp(A[j], A[j - 1])) {
                point t = A[j];
                A[j] = A[j - 1];
                A[j - 1] = t;
            }
}

int unique(point A[], int n) {
    int t = 0;
    for (int i = 0; i < n; i++)
        if (②)
            A[t++] = A[i];
    return t;
}

bool binary_search(point A[], int n, int x, int y) {
    point p;
    p.x = x;
    p.y = y;
    p.id = n;
    int a = 0, b = n - 1;
    while (a < b) {
        int mid = ③;
        if (④)
            a = mid + 1;
        else
            b = mid;
    }
    return equals(A[a], p);
}

const int MAXN = 1000;
point A[MAXN];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> A[i].x >> A[i].y;
        A[i].id = i;
    }
    sort(A, n);
    n = unique(A, n);
    int ans = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (⑤ && binary_search(A, n, A[i].x, A[j].y) &&
                binary_search(A, n, A[j].x, A[i].y)) {
                ans++;
            }
    cout << ans << endl;
    return 0;
}

⑤处应填 ( )

选项

• A. A[i].x == A[j].x
• B. A[i].id < A[j].id
• C. A[i].x == A[j].x && A[i].id < A[j].id
• D. A[i].x < A[j].x && A[i].y < A[j].y

答案

D

题解

选 D：

``cpp A[i].x < A[j].x && A[i].y < A[j].y ``

程序用 A[i] 和 A[j] 作为矩形的一对对角顶点，再用两次二分查找检查另外两个顶点是否存在：

• (A[i].x, A[j].y)
• (A[j].x, A[i].y)

⑤要求 A[i] 位于 A[j] 的左下方，有两个作用：

1. 保证矩形有面积：横坐标、纵坐标都不同，排除退化情况。
2. 避免重复计数：每个矩形只有一组“左下角 → 右上角”，所以恰好统计一次。

B 只限制编号顺序，既不能排除退化情况，也不能避免同一个矩形被两条对角线各统计一次；A、C 则要求横坐标相同，无法作为正常矩形的对角顶点。