题库 模拟押题卷 题目列表 (矩形计数)平面上有n个关键点,求有多少个四条边都...
组合题

(矩形计数)平面上有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 = 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;
}

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[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++;
}
printf("%d\n", ans);
return 0;
}

①处应填()

②处应填()

③处应填()

④处应填()

⑤处应填()

1.

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)

2.

A.i == 0 || cmp(A[i], A[i - 1])

B.t == 0 || equals(A[i], A[t - 1])

C.i == 0 || !cmp(A[i], A[i - 1])

D.t == 0 || !equals(A[i], A[t - 1])

3.

A.b - (b - a) / 2 + 1

B.(a + b + 1) >> 1

C.(a + b) >> 1

D.a + (b - a + 1) / 2

4.

A.!cmp(A[mid], p)

B.cmp(A[mid], p)

C.cmp(p, A[mid])

D.!cmp(p, A[mid])

5.

A.A[i].x == A[j].x

B.A[i].id < A[j].id

C.A[i].x == A[j].x && A[i].id < A[j].id

D.A[i].x < A[j].x && A[i].y < A[j].y

第一空(3分):_______________________

第二空(3分):_______________________

第三空(3分):_______________________

第四空(3分):_______________________

第五空(3分):_______________________

第 1 题 填空
第 2 题 填空
第 3 题 填空
第 4 题 填空
第 5 题 填空
题目信息
阅读程序
-
正确率
0
评论
84
点击
QQ
微信