20(矩形计数)平面上有n个关键点,求有多少个四条边都和x轴或者y轴平行的矩形,满足四个顶点都是关键点。给出的关键点可能有重复,但完全重合的矩形只计一次。
试补全枚举算法。
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 }
①处应填()
②处应填()
③处应填()
④处应填()
⑤处应填()
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