← 查看本卷题目
组合题5 个小题
已作答 0 / 5

( 2 ) (矩形计数) 平面上有 nn 个关键点,求有多少个四条边都和 xx 轴或者 yy 轴平行的矩形,满足四个顶点都是关键点。给出的关键点可能有重复,但完全重合的矩形只计一 次。

试补全枚举算法。

 #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;}
第 42 题单选题原卷 3 分

④处应填 ( )

填写答案