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

题目

（ 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.x != b.x ? a.x < b.x : a.id < b.id
• B. a.x != b.x ? a.x < b.x : a.y < b.y
• C. equals(a, b) ? a.id < b.id : a.x < b.x
• D. equals(a, b) ? a.id < b.id : (a.x != b.x ? a.x < b.x : a.y < b.y)

答案

B

题解

选 B：

``cpp a.x != b.x ? a.x < b.x : a.y < b.y ``

意思是按坐标排序：

• x 不同，按 x 从小到大排；
• x 相同，按 y 从小到大排。

例如，排序后可以是：

``text (1, 2), (1, 2), (1, 5), (2, 1), (2, 3) ``

这样，坐标相同的点会相邻，便于后面的 unique 去重；同时，点按坐标有序，也便于二分查找。

为什么不选 D？

D 还会在坐标相同时比较 id。注意二分查找中构造的目标点：

``cpp p.id = n; ``

若后面的④按通常写法填 cmp(A[mid], p)，即使 A[mid] 与 p 坐标相同，也可能因为编号更小而被判断为“小于目标”，导致查找跳过正确位置。

因此，这里的比较应只依据 x、y 坐标，不应把输入编号 id 加入排序条件。