题目
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1696
题意
平面上有n个整数点，找一个矩形，使得边界上包含尽量多的点。
思路
如刘书
首先可以按照x对所有点排序，然后枚举矩形左右边界
确定左右边界之后，接下来就可以枚举下边界，直接求最优上边界。
当左右下边界确定后，就能知道图中粉色部分上有多少个点，但这样离求出带上边界的矩形上有多少个点还差一点。如图，假如上边界是淡绿色边，那么还需要去掉紫色的两段左右边界上不属于矩形的前缀，再加上上边界上橙色的那段。
如何求最优上边界呢？明显，最优上边界和下边界无关，只与自身的x和左右边界有关。所以我们可以直接记录目前为止的最优上边界-也就是记录橙色部分的点减去紫色前缀中点后还剩下点的最大值-该最大值对应的就是最优上边界。
假设左边界对应ymin,右边界ymax，那么对于一条横边x = x0，设cntcorner为左右边界与横边相交位置上存在的点，cnt为左右边界夹住（不包括相交位置）的点。prefix为cntcorner累计值，也即y=ymin或ymax，x <= x0的点数，那么粉色的部分=prefix + cnt，
设另外一条横边x = x1, x1 < x0为上边界，对应cnt', cntcorner'和prefix‘，那么此时矩形上的点就是prefix + cnt + cnt' - prefix' - cntcorner'
cnt' - prefix' - cntcorner'的最大值对应最优上边界。
代码
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#define LOCAL_DEBUG
using namespace std;
const int MAXN = 1e2 + ;
typedef pair<int, int> MyPair;
MyPair pt[MAXN];
int y[MAXN];
int n; int check(int ymin, int ymax) {
int reserve = , ans = ;
for (int i = , ygap = ; i < n;) {
if (pt[i].second < ymin || pt[i].second > ymax) {
i++; continue;
}
int x = pt[i].first;
int cnt = , cntcorner = ;
for (int j = i; j < n && pt[j].first == x && pt[j].second <= ymax && pt[j].second >= ymin; i++, j++) {
if (pt[j].second == ymin || pt[j].second == ymax)cntcorner++;
else cnt++;
}
ans = max(ans, reserve + cnt + cntcorner + ygap);
reserve = max(reserve, cnt - ygap);
ygap += cntcorner;
}
return ans;
} int main() {
#ifdef LOCAL_DEBUG
freopen("C:\\Users\\Iris\\source\\repos\\ACM\\ACM\\input.txt", "r", stdin);
//freopen("C:\\Users\\Iris\\source\\repos\\ACM\\ACM\\output.txt", "w", stdout);
#endif // LOCAL_DEBUG
//int T;
// scanf("%d", &T);
for (int ti = ;scanf("%d", &n) == && n; ti++) {
for (int i = ; i < n; i++) {
scanf("%d%d", &pt[i].first, &pt[i].second);
y[i] = pt[i].second;
}
sort(pt, pt + n);
sort(y, y + n);
int ynum = ;
for (int i = ; i < n; i++) {
if (i && y[i] == y[i - ]) {
continue;
}
else {
y[ynum++] = y[i];
}
}
int ans = -;
if (ynum <= )ans = n;
else {
for (int i = ; i < ynum; i++) {
for (int j = i + ; j < ynum; j++) {
ans = max(ans, check(y[i], y[j]));
}
}
}
printf("Case %d: %d\n", ti, ans);
} return ;
}