CSP-J 入门级 · CSP 2021 入门级第一轮 第 20 题

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

#include <iostream>
using namespace std;

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

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

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

void sort(struct 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])) {
                struct point t = A[j];
                A[j] = A[j - 1];
                A[j - 1] = t;
            }
}

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

bool binary_search(struct point A[], int n, int x, int y) {
    struct point p;
    p.x = x;
    p.y = y;
    p.id = n;
    int a = 0, b = n - 1;
    while (

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题核心就是枚举对角点，先按x后按y排序去重，再二分查另外两个角。

最容易栽跟头在去重逻辑上，很多人会把cmp(A[i], A[i-1])直接套进去，其实unique函数里是要和已经保留下来的新数组末尾比较，而且判断条件要取反，保留不重复的。另外枚举时若没加x<y且y<x的严格限制，会重复数矩形，或者漏掉某些情况，一定要记住只枚举左下和右上对角。

这道题考查的是结构体排序、去重、二分查找以及枚举对角点判断矩形存在性。命题人喜欢把多个基础操作揉在一起，尤其是去重时的边界判断和比较函数细节，这是典型的挖坑点。拿到题先想：矩形四个顶点已知两个对角点就能确定，所以只要枚举所有可能的对角点对，再检查另外两个顶点是否存在即可。但题目要求完全重合的矩形只计一次，所以必须先对点去重，且排序规则要能支持去重后的有序性。

首先看排序。cmp函数决定了点的顺序，去重时要能判断两个点是否相同，所以比较规则必须包含坐标和ID。选项D把equals放前面，若相同则按ID排序，否则先比x再比y，这样排序稳定且能配合unique去重，选D。

接着是unique。去重时不能和原数组的前一个比，因为原数组可能还有重复，而是要和已经放入新数组的最后一个元素A[t-1]比，且条件要取反，保留不重复的，所以选D。

二分查找部分，mid计算是经典写法，(a+b) >> 1即可，选C。判断mid点与目标点的大小关系时，若mid点小于目标，则目标在右半，a=mid+1，否则b=mid，所以cmp(A[mid], p)选B。

枚举对角点时，为了避免重复计数，必须固定左下和右上，即A[i].x < A[j].x && A[i].y < A[j].y，选D。

考频方面，结构体在题库中非常常见，37题覆盖多个级别，近年GESP八级、六级、四级都有，说明这类题目是高频考点。枚举法更是基础中的基础，159题覆盖广，CSP入门级尤其爱考。二分查找39题，GESP五级、七级、CSP入门级都有，属于必会技能。综合来看，这类组合题在未来几年仍会持续出现，尤其是GESP六级、四级和CSP入门级，命题人可能会在排序规则或去重逻辑上继续挖坑，比如加入更多维度或更复杂的比较函数。

暂无足够依据预测具体年份和题目，但建议重点练习结构体排序、去重和二分查找的组合应用，尤其是unique函数的边界处理，这是最容易出错的地方。