2021 CSP-J 完善程序3
1 完善程序 (单选题 ，每小题3分，共30分)
(矩形计数)平面上有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 0;
}
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;
}39.①处应填( )
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)
40.②处应该填( )
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])
41.③处应该填( )
A. b-(b-a)/2+1
B. (a+b+1)>>1
C. (a+b)>>1
D. a+(b-a+1)/2
42.④处应该填( )
A. !cmp(A[mid],p)
B. cmp(A[mid],p)
C. cmp(p,A[mid])
D. !cmp(p,A[mid])
43.⑤处应该填( )
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
2 相关知识点
1) 冒泡排序
冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端
n个元素的冒泡排序，需要n趟完成，
每趟进行逐一两两比较，进行n-1次比较，把最大(最小)元素比较出来，交换到最后
2) 数组去重
排好序的数字，相同元素是紧挨着的，当前加入的元素时如果和上一元素相同，需要过滤掉
3) 二分查找中间值
/* 向右逼近，如果找到满足条件的数，会继续向右找更大的数
mid=(left+right)/2 left和right都接近最大值时，可能溢出可以使用下面写法替换
mid=left + (right-left) / 2;
可以求满足条件的最大值
*/
/* 向左逼近，如果找到满足条件的数，会继续向左找更小的数
mid=(left+right+1)/2 left和right都接近最大值时，可能溢出可以使用下面写法替换
mid=left + (right-left+1) / 2;
可以求满足条件的最小值
*/
4) 二分找边界
//左闭右闭 while left right 最终left=right+1
while(left<=right) left = mid + 1; right =mid-1;
//左闭右开 while left right 最终left=right
while(left<right) left = mid + 1; right =mid;
//左开右闭 while left right 最终left=right
while(left<right) left=mid; right=mid+1;
//左开右开 while left right 最终left=right-1
while(left+1<right) left=mid; right=mid;5) 位运算
左移
//左移 x<<1 x左移1位，对应x变为原来2倍
#include<bits/stdc++.h>
using namespace std;
int main(){
int x=2;
x=x>>1;//x变为原来2倍
cout<<x;//输出4
return 0;
}右移
#include<bits/stdc++.h>
using namespace std;
int main(){
int x=2;
x=x>>1;//x变为原来1/2
cout<<x<<endl;//输出1
x=5;
x=x>>1;//x变为原来1/2,向下取整 为2
cout<<x;//输出2
return 0;
}6) 点确定矩形
在矩形中，通过对角线2点，可以找到另一对角线两点坐标
例如
已知黑色点A[i]和黑色点A[j]
则 A[i].x,A[j].y 为左上方的红色点，A[j].x,A[i].y为右下方红色的点
如果通过黑色的2点，可以找到红色的2点，则此4点组成的矩形是长方形
3 思路分析
39.①处应填( B )
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)
分析
排序的点中，x和y具有位置信息，id从程序看没做特殊处理
主要和x和y坐标有关，不需要对id比较
选B，x不同按x比较，后面参数x大返回true，影响后面排序从小到大
x相同按y比较，后面参数y大返回true，影响后面排序从小到大
40.②处应该填( D )
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])
分析
去重逻辑
t==0时，此时是第1个不会重复，直接覆盖添加A[t]
当前A[i]和上1次覆盖添加到A数组的A[t-1]比较，不相同添加
所以是!equals(A[i],A[t-1])，选D
41.③处应该填( C )
A. b-(b-a)/2+1
B. (a+b+1)>>1
C. (a+b)>>1
D. a+(b-a+1)/2
分析
/*
根据如下代码可知，左闭右开向右递进
mid计算时，需要向下取整
选项C (a+b)>>1 等同 (a+b)/2 ,对(a+b)/2 向下取整
其他3个选项都是向上取整
*/
while(a<b){
int mid=③;
if(④)
a=mid+1;//向右递进
else
b=mid;
}
42.④处应该填( B )
A. !cmp(A[mid],p)
B. cmp(A[mid],p)
C. cmp(p,A[mid])
D. !cmp(p,A[mid])
分析
/*
根据如下代码可知，左闭右开向右递进
向右递进
如果中间值a[mid]比目标值p小，继续向右找，直到找到为止
while循环结束在a==b
*/
while(a<b){
int mid=③;
if(④)
a=mid+1;//向右递进
else
b=mid;
}3.⑤处应该填( D )
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
分析
由下图可知， 如果知道对角线2个黑点，可以通过2个二分查找，找到2个对应红点组成一个矩形
binary_search(A,n,A[i].x,A[j].y)
binary_search(A,n,A[j].x,A[i].y)
2个黑点是对角线，需要确保2黑点的x和y都不相等，只有D选项符合2黑点的x和y都不相等
