CSPJ2021 完善程序2
(矩形计数）平面上有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 ___(1)___;
}
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 (___(2)___)
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 = ___(3)___;
if (___(4)___)
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 ( ___(5)___ && 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;
}
阅读程序，补全代码
①处应填（）
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)
②处应填（）
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])
③处应填（）
b – (b – a) / 2 + 1
(a + b + 1) >> 1
(a + b) >> 1
a + (b – a + 1) / 2
④处应填（）
!cmp(A[mid], p)
cmp(A[mid], p)
cmp(p, A[mid])
!cmp(p, A[mid])
⑤处应填（）
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
发表评论