#cspjc2021w2. 2021csp-j初赛完善程序2

2021csp-j初赛完善程序2

2021csp-j初赛完善程序2

每小题3 分

1.第二题

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

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.①处应填( ){{ select(1) }}

  • a.x != b.x ? a.x < b.x : a.id < b.id
  • a.x != b.x ? a.x < b.x : a.y < b.y
  • equals(a, b) ? a.id < b.id : a.x < b.x
  • equals(a, b) ? a.id < b.id : (a.x != b.x ? a.x < b.x : a.y < b.y)

2.②处应填( ){{ select(2) }}

  • i == 0 || cmp(A[i], A[i - 1])
  • t == 0 || equals(A[i], A[t - 1])
  • i == 0 || !cmp(A[i], A[i - 1])
  • t == 0 || !equals(A[i], A[t - 1])

3.③处应填( ) {{ select(3) }}

  • b - (b - a) / 2 + 1
  • a + b + 1) >> 1
  • (a + b) >> 1
  • a + (b - a + 1) / 2

4.④处应填( ) {{ select(4) }}

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

5.⑤处应填( ) {{ select(5) }}

  • A[i].x == A[j].x
  • A[i].id < A[j].id
  • A[i].x == A[j].x && A[i].id < A[j].id
  • A[i].x < A[j].x && A[i].y < A[j].y