UVaLive 3695 Distant Galaxy (扫描线)

题意：给平面上的 n 个点，找出一个矩形，使得边界上包含尽量多的点。

析：如果暴力那么就是枚举上下边界，左右边界，还得统计个数，时间复杂度太高，所以我们考虑用扫描线来做，枚举上下边界，

然后用其他方法来确定左右边界。我们定义left[i] 表示竖线左边位于上下边界上的点数（不包含在竖线上的点），on[i]表示竖线 i 上的点，

但不包含上下边界上的点，in[i]表示竖线 i 的上的点，但是包含上下边界上的点。那么我们可以递推。最后矩形边界上的点数为

left[i] - left[j] + on[i] + in[j]，然后如果右边界 j 确定了，那么要 on[i] - in[i] 最大这个是不断更新 left[i] = left[i-1] + in[i-1] - on[i-1]。

代码如下：

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <cstring>
#include <set>
#include <queue>
#include <algorithm>
#include <vector>
#include <map>
#include <cctype>
#include <cmath>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#define debug() puts("++++");
#define freopenr freopen("in.txt", "r", stdin)
#define freopenw freopen("out.txt", "w", stdout)
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const double inf = 0x3f3f3f3f3f3f;
const double PI = acos(-1.0);
const double eps = 1e-8;
const int maxn = 100 + 5;
const int mod = 2000;
const int dr[] = {-1, 1, 0, 0};
const int dc[] = {0, 0, 1, -1};
const char *de[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"};
int n, m;
const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
inline bool is_in(int r, int c){
    return r >= 0 && r < n && c >= 0 && c < m;
}

struct Point{
    int x, y;
    bool operator < (const Point &p) const{
        return x < p.x;
    }
};
Point a[maxn];
int l[maxn], on[maxn], in[maxn], y[maxn];

int solve(){
    sort(a, a + n);
    sort(y, y + n);
    int ans = 0;
    m = unique(y, y + n) - y;
    if(m <= 2)  return n;

    for(int y1 = 0; y1 < m; ++y1)
        for(int y2 = y1 + 1; y2 < m; ++y2){
            int k = 0;
            for(int i = 0; i < n; ++i){
                if(!i || a[i].x != a[i-1].x){
                    ++k;
                    l[k] = !i ? 0 : l[k-1] + in[k-1] - on[k-1];
                    on[k] = in[k] = 0;
                }
                if(a[i].y > y[y1] && a[i].y < y[y2])  ++on[k];
                if(a[i].y >= y[y1] && a[i].y <= y[y2])  ++in[k];
            }
            if(k <= 2)  return n;

            int mmax = 0;
            for(int i = 1; i <= k; ++i){
                ans = max(ans, l[i] + in[i] + mmax);
                mmax = max(mmax, on[i] - l[i]);
            }
        }
    return ans;
}

int main(){
    int kase = 0;
    while(scanf("%d", &n) == 1 && n){
        for(int i = 0; i < n; ++i){
            scanf("%d %d", &a[i].x, &a[i].y);
            y[i] = a[i].y;
        }
        printf("Case %d: %d
", ++kase, solve());
    }
    return 0;
}