题库 信息学奥赛题库 题目列表 (矩形计数)平面上有n个关键点,求有多少个四条边都...
组合题

(矩形计数)平面上有n个关键点,求有多少个四条边都和x轴或者y轴平行的矩形,满足四个顶点都是关键点。给出的关键点可能有重复,但完全重合的矩形只计一次。试补全枚举算法。

#include <iostream>
using namespace std;
struct point {
  int x, y, id;
};

bool equals(point a, point b){
  return a.x== b.x && a.y == b.y;
}
bool cmp (point a,point b){
  return a.x!=b.x?a.x<b.x:a.y<b.y; 
}

void sort(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])) {
            point t = A[j];
            A[j] =A[j-1];
            A[j -1] =t;
          }
}

int unique (point A[],int n){
  int t= 0;
  for(int i= 0; i < n; i++)
      if(②)
         A[t++]=A[i];
     return t;
}

bool binary_search(point A[], int n, int x ,int y){
  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);
}

const int MAXN = 1000;
point A [MAXN];
int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; i++){
    cin >> 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++;
          }
        cout << ans << endl;    
  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
题目信息
完善程序 2021年 初赛
-
正确率
0
评论
187
点击