题目信息

题目类型
入门级
题目年份
2021
题目题型
综合题
关 键 词
矩形计数

题目题干

20(矩形计数)平面上有n个关键点,求有多少个四条边都和x轴或者y轴平行的矩形,满足四个顶点都是关键点。给出的关键点可能有重复,但完全重合的矩形只计一次。vnL100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
试补全枚举算法。vnL100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

1 	#include <stdio.h>
2 
3 	struct point {
4 		int x, y, id;
5 	};
6 
7 	int equals(struct point a, struct point b){
8 		return a.x == b.x && a.y == b.y;
9 	}
10
11	int cmp(struct point a, struct point b){
12		return  ①; 
13	}
14
15	void sort(struct point A[], int n){
16		for (int i = 0; i < n; i++)
17			for (int j = 1; j < n; j++)
18				if (cmp(A[j], A[j - 1])){
19					struct point t = A[j];
20					A[j] = A[j - 1];
21					A[j - 1] = t;
22				}
23	}
24
25	int unique(struct point A[], int n){
26		int t = 0;
27		for (int i = 0; i < n; i++)
28			if (②)
29				A[t++] = A[i];
30		return t;
31	}
32
33	int binary_search(struct point A[], int n, int x, int y){
34		struct point p;
35		p.x = x;
36		p.y = y;
37		p.id = n;
38		int a = 0, b = n - 1;
39		while(a < b){
40			int mid = ③;
41			if (④)
42				a = mid + 1;
43			else 
44				b = mid; 
45		}
46			return equals(A[a], p);
47	}
48
49	#define MAXN 1000
50	struct point A[MAXN];
51
52	int main(){
53		int n;
54		scanf("%d", &n);
55		for (int i = 0; i < n; i++){
56			scanf("%d %d", &A[i].x, &A[i].y);
57			A[i].id = i;
58		}
59		sort(A, n);
60		n = unique(A, n);
61		int ans = 0;
62		for (int i = 0; i < n; i++)
63			for (int j = 0; j < n; j++)
64			if ( ⑤ && binary_search(A, n, A[i].x, A[j].y) && binary_search(A, n, A[j].x, A[i].y)){
65							ans++;
66			}
67		printf("%d\n", ans); 
68		return 0;
69	}

          

①处应填()vnL100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
②处应填()vnL100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
③处应填()vnL100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
④处应填()vnL100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
⑤处应填()vnL100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
1.vnL100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
A.a.x != b.x ? a.x < b.x : a.id < b.idvnL100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
B.a.x != b.x ? a.x < b.x : a.y < b.yvnL100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
C.equals(a,b) ? a.id < b.id : a.x < b.xvnL100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
D.equals(a,b) ? a.id < b.id : (a.x != b.x ? a.x < b.x : a.y < b.y)vnL100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
2.vnL100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
A.i == 0 || cmp(A[i], A[i - 1])vnL100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
B.t == 0 || equals(A[i], A[t - 1])vnL100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
C.i == 0 || !cmp(A[i], A[i - 1])vnL100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
D.t == 0 || !equals(A[i], A[t - 1])vnL100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
3.vnL100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
A.b - (b - a) / 2 + 1vnL100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
B.(a + b + 1) >> 1vnL100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
C.(a + b) >> 1vnL100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
D.a + (b - a + 1) / 2vnL100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
4.vnL100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
A.!cmp(A[mid], p)vnL100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
B.cmp(A[mid], p)vnL100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
C.cmp(p, A[mid])vnL100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
D.!cmp(p, A[mid])vnL100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
5.vnL100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
A.A[i].x == A[j].xvnL100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
B.A[i].id < A[j].idvnL100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
C.A[i].x == A[j].x && A[i].id < A[j].idvnL100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
D.A[i].x < A[j].x && A[i].y < A[j].yvnL100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

答案解析

相关题目

20(矩形计数)平面上有n个关键点,求有多少个四条边都和x轴或者y轴平行的矩形,满足四个顶点都是关键点。给出的关键点可能有重复,但完全重合的矩形只计一次。 试补全枚举算法。 1 #include
第19 (Josephus 问题)有 n个人围成一个圈,依次标号 0 至n-1。从 0 号开始,依次 0, 1, 0, 1, … 交替报数,报到 1 的人会离开,直至圈中只剩下一个人。求最后剩下人的编
第 18 #include <iostream>     using namespace std;        const int n = 100000;    const int N 
第17 题  #include <iostream>     #include <string>     using namespace std;          char 
第 1题  #include <iostream>     using namespace std;     int n;     int a[1000];         int f(i
第 15 题 有四个人要从 A 点坐一条船过河到 B 点,船一开始在 A 点。该船一次最多可坐两个人。 已知这四个人中每个人独自坐船的过河时间分别为1,2,4,8,且两个人坐船的过河时间为两人独自过河
第 14 题 以 a为起点,对下边的无向图进行深度优先遍历,则 b,c,d,e 四个点中有可能作为最后一个遍历到的点的个数为( )。   A. 1  B. 2  C. 3  D. 4
第 13 题 考虑如下递归算法 solve(n)         if n<=1 return 1          else if n>=5 return n*solve(n-2) 
第 12 题 由 1,1,2,2,31,1,2,2,3 这五个数字组成不同的三位数有( )种。  A. 18  B. 15  C. 12  D. 24
第 11 题 在数据压缩编码中的哈夫曼编码方法,在本质上是一种( )的策略。  A. 枚举  B. 贪心  C. 递归  D. 动态规划

提示声明

  • 免责声明:本站资源均来自网络或者用户投稿,仅供用于学习和交流:如有侵权联系删除!
  • 温馨提示:本文属于积分文章,需要充值获得积分或升级VIP会员,也可在会员中心投稿获取。

猜你喜欢