组合题

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

试补全枚举算法。

01 #include <iostream>

02 

03 using namespace std;

04 

05 struct point {

06 int x, y, id;

07 };

08 

09 bool equals(point a, point b) {

10 return a.x == b.x && a.y == b.y;

11 }

12 

13 bool cmp(point a, point b) {

14 return ①;

15 }

16 

17 void sort(point A[], int n) {

18 for (int i = 0; i < n; i++)

19 for (int j = 1; j < n; j++)

20 if (cmp(A[j], A[j - 1])) {

21 point t = A[j];

22 A[j] = A[j - 1];

23 A[j - 1] = t;

24 }

25 }

26

28 int t = 0;

29 for (int i = 0; i < n; i++)

30 if (②)

31 A[t++] = A[i];

32 return t;

33 }

34 

35 bool binary_search(point A[], int n, int x, int y) {

36 point p;

37 p.x = x;

38 p.y = y;

39 p.id = n;

40 int a = 0, b = n - 1;

41 while (a < b) {

42 int mid = ③;

43 if (④)

44 a = mid + 1;

45 else

46 b = mid;

47 }

48 return equals(A[a], p);

49 }

50 

51 const int MAXN = 1000;

52 point A[MAXN];

53 

54 int main() {

55 int n;

56 cin >> n;

57 for (int i = 0; i < n; i++) {

58 cin >> A[i].x >> A[i].y;

59 A[i].id = i;

60 }

61 sort(A, n);

62 n = unique(A, n);

63 int ans = 0;

64 for (int i = 0; i < n; i++)

65 for (int j = 0; j < n; j++)

66 if (⑤ && binary_search(A, n, A[i].x, A[j].y) && 

binary_search(A, n, A[j].x, A[i].y)) {

67 ans++;

68 }

69 cout << ans << endl;

70 return 0;

71 }

第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

赣ICP备20007335号-2