组合题5 个小题
已作答 0 / 5
( 2 ) (矩形计数) 平面上有 n 个关键点,求有多少个四条边都和 x 轴或者 y 轴平行的矩形,满足四个顶点都是关键点。给出的关键点可能有重复,但完全重合的矩形只计一 次。
试补全枚举算法。
1 2#include <iostream>3using namespace std;4 5struct point {6 int x, y, id;7};8 9bool equals(point a, point b) {10 return a.x == b.x && a.y == b.y;11}12 13bool cmp(point a, point b) {14 return ①;15}16 17void sort(point A[], int n) {18 for (int i = 0; i < n; i++)19 for (int j = 1; j < n; j++)20 if (cmp(A[j], A[j - 1])) {21 point t = A[j];22 A[j] = A[j - 1];23 A[j - 1] = t;24 }25}26 27int unique(point A[], int n) {28 int t = 0;29 for (int i = 0; i < n; i++)30 if (②)31 A[t++] = A[i];32 return t;33}34 35bool binary_search(point A[], int n, int x, int y) {36 point p;37 p.x = x;38 p.y = y;39 p.id = n;40 int a = 0, b = n - 1;41 while (a < b) {42 int mid = ③;43 if (④)44 a = mid + 1;45 else46 b = mid;47 }48 return equals(A[a], p);49}50 51const int MAXN = 1000;52point A[MAXN];53 54int main() {55 int n;56 cin >> n;57 for (int i = 0; i < n; i++) {58 cin >> A[i].x >> A[i].y;59 A[i].id = i;60 }61 sort(A, n);62 n = unique(A, n);63 int ans = 0;64 for (int i = 0; i < n; i++)65 for (int j = 0; j < n; j++)66 if (⑤ && binary_search(A, n, A[i].x, A[j].y) &&67 binary_search(A, n, A[j].x, A[i].y)) {68 ans++;69 }70 cout << ans << endl;71 return 0;72}③处应填 ( )