题目大意
N 个点（N≤100），求轴平行矩形，使边界上点数最多。输出最大点数。
枚举上下边界 + 扫描线
- 离散化 Y 坐标，枚举上边界
y_max 和下边界 y_min
- 按 X 排序点，左到右扫描
- 维护数组：
on[i]：第 i 个 X 坐标严格内部（y_min
on2[i]：第 i 个 X 坐标闭区间（y_min≤y≤y_max）的点数L[i]：第 i 条竖线左侧边界上的点数（含左边界）
- 枚举右边界，更新答案：
ans = max(ans, L[i] + on2[i] + max_{j
C++ 实现
#include
#include
using namespace std;
struct Pt { int x, y; };
Pt p[1005];
int y[1005], on[1005], on2[1005], L[1005];
int n;
int solve() {
sort(p, p+n, [](Pt a, Pt b){ return a.x < b.x; });
for (int i=0;i1) L[k] = L[k-1] + on2[k-1] - on[k-1];
}
if (p[i].y > ymin && p[i].y < ymax) on[k]++;
if (p[i].y >= ymin && p[i].y <= ymax) on2[k]++;
}
if (k <= 2) return n;
int best = 0;
for (int i=1; i<=k; ++i) {
ans = max(ans, L[i] + on2[i] + best);
best = max(best, on[i] - L[i]);
}
}
return ans;
}
int main() {
int cas=1;
while (scanf("%d", &n), n) {
for (int i=0;i
复杂度
- 枚举 Y 对：O(m²) ≤ 100² = 10,000
- 每对扫描：O(n) ≤ 100
- 总计：~1e6 操作，极快
关键技巧
- 离散化 Y：仅考虑点的实际 Y 坐标作为边界
- 扫描线维护 L/on/on2：O(1) 更新左侧边界贡献
- 特判 m≤2：所有点共线，全在边界上
