①处应填()
(矩形计数)平面上有n个关键点,求有多少个四条边都和x轴或者y轴平行的矩形,满足四个顶点都是关键点。给出的关键点可能有重复,但完全重合的矩形只计一次。 试补全枚举算法。
#include <stdio.h>
struct point {
int x, y, id;
};
int equals(struct point a, struct point b) {
return a.x == b.x && a.y == b.y;
}
int 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 = i; 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 + 1;
}
int 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(a < b) {
int mid = 第三处;
if (第四处)
a = mid + 1;
else
b = mid;
}
return equals(A[a], p);
}
#define MAXN 1000
struct point A[MAXN];
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d %d", &A[i].x, &A[i].y);
A[n].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 (i < j && binary_search(A, n, A[i].x, A[j].y) &&
binary_search(A, n, A[j].x, A[i].y))
ans++;
printf("%d\n", ans);
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)