Input
There are multiple test cases in the input file. Each test case starts with one integer N, (1 ≤ N ≤ 100),
the number of star systems on the telescope. N lines follow, each line consists of two integers: the X
and Y coordinates of the K-th planet system. The absolute value of any coordinate is no more than
10 9 , and you can assume that the planets are arbitrarily distributed in the universe.
N = 0 indicates the end of input file and should not be processed by your program.
Output
For each test case, output the maximum value you have found on a single line in the format as indicated
in the sample output.
Sample Input
10
2 3
9 2
7 4
3 4
5 7
1 5
10 4
10 6
11 4
4 6
0
Sample Output
Case 1: 7

看到乱序的点应该想到排序,上下边界确定后,横向扫应该想到递推,时间复杂度为O(N^3)

#include <cstdio>
#include <algorithm>
#include <iostream> #define N 101 int Left[N], on[N], on2[N], y[N], n, ans, kase = ; struct Point {
int x, y; bool operator<(const Point &rhs) const {
return x <= rhs.x;
}
} P[N]; int solve(); using namespace std; int main() {
while (cin >> n && n) {
for (int i = ; i < n; ++i) {
cin >> P[i].x >> P[i].y;
y[i] = P[i].y;
}
printf("Case %d: %d\n", ++kase, solve());
} } int solve() {
ans = , sort(P, P + n), sort(y, y + n);
int m = unique(y, y + n) - y;
if (m <= )
return n;
for (int i = ; i < m; ++i) {
for (int j = i + ; j < m; ++j) { //确定上下边界
int y1 = y[i], y2 = y[j], k = , t = , M = ; for (; t < n; ++t) { //预扫描,递推获得left,on,on2数组的值
if (t == || P[t].x != P[t - ].x) {
k++;
on[k] = on2[k] = ;
Left[k] = Left[k - ] + on2[k - ] - on[k - ];
}
if (y1 < P[t].y && P[t].y < y2) //c++是不让连写的
on[k]++;
if (y1 <= P[t].y && P[t].y <= y2)
on2[k]++;
}
for (t = ; t <= k; ++t) {
ans = max(on2[t] + Left[t] + M, ans);
M = max(on[t] - Left[t], M);
}
}
}
return ans;
}
05-11 09:36
查看更多