UVa 1382 - Distant Galaxy

Published on 2016-02-02

题目地址

描述

平面上有 n(n100)n(n\le100) 个点,请你找出一个矩形,使得的边界上包含尽量多的点。输出边界上最多有多少个点。

样例输入

10
2 3
9 2
7 4
3 4
5 7
1 5
10 4
10 6
11 4
4 6
0

样例输出

Case 1: 7

分析

排除边界情况,如果点全部分布在两行或者两列,肯定能够全部覆盖,答案为 nn
分析可得,最优最小矩形的每一条边都有至少一个点(角上的点同时属于两条边)。很好证明,假如某一条边上没有点,那么这一条边的上面或者下面必定有点(要不然就属于边界情况),如果在上面,那么增加矩形面积,覆盖到上面的点可以更优;如果在下面,我们可以使得这条边相邻两条边的某个点卡在角上,使得这条边上有点。
因此得到一个暴力算法:枚举四条边界经过的点,统计经过的点数,复杂度 O(n5)O(n^5),不足以通过本题。
可以试着只枚举上下边界,再通过不那么'暴力'的方法得到最优的左右边界。
我们枚举上下边界,问题就转化为找到最优的左右边界,使得在边上的点数最大。我们将所有点不同的 xx 坐标看成一条竖线。
将所有点从左到右扫一遍,得到以下信息:
left[i]\mathrm{left}[i] 表示竖线 ii 左边(不包括竖线 ii)且在上下边界上的点的个数。
on[i]\mathrm{on}[i] 表示竖线 ii 上的所有点的纵坐标在上下边界(不包含在上下边界上)内的点的个数。
on2[i]\mathrm{on2}[i] 表示竖线 ii 上的所有点的纵坐标在上下边界(包含在上下边界上)内的点的个数。
枚举右边界 jj, 如果左边界是 ii,答案是 max(left[j]left[i]+on2[j]+on[i])\max(\mathrm{left}[j] - \mathrm{left}[i] + \mathrm{on2}[j] + \mathrm{on}[i]),注意到 ii 一定在 jj 右边,所以从左到右枚举 jj 的过程中先更新自己,再顺便维护 val=max(on[i]left[i],i<j)\mathrm{val} = \max(\mathrm{on}[i] - \mathrm{left}[i], i < j) 即可。

代码

//  Created by Sengxian on 2/2/16.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  UVa 1382 扫描法
#include <algorithm>
#include <iostream>
#include <climits>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#define br putchar('\n')
using namespace std;

inline int ReadInt() {
    int n = 0, ch = getchar(); bool flag = false;
    while(ch < '0' || ch > '9') {
        if(ch == '-') flag = true;
        ch = getchar();
    }
    do {
        n = n * 10 + ch - '0';
        ch = getchar();
    }while(ch >= '0' && ch <= '9');
    return flag ? -n : n;
}

const int maxn = 100 + 3;
struct Point {
    int x, y;
    bool operator < (const Point &p) const {
        return x < p.x;
    }
}Points[maxn];
int n, y[maxn], leftCnt[maxn], onCnt[maxn], on2Cnt[maxn];

int Solve() {
    int m, ans = 0;
    sort(y, y + n);
    m = unique(y, y + n) - y;
    if(m <= 2) return n; //横线不足两条,上下边界直接可以包含所有点
    sort(Points, Points + n);
    for(int a = 0; a < m; ++a)
        for(int b = a + 1; b < m; ++b) {
            //枚举上下边界
            int ymin = y[a], ymax = y[b];
            int k = 0; //记录有多少条竖线
            for(int i = 0; i < n; ++i) {
                if(i == 0 || Points[i].x != Points[i - 1].x) {
                    k++;
                    onCnt[k] = on2Cnt[k] = 0;
                    leftCnt[k] = k == 0 ? 0 : leftCnt[k - 1] + on2Cnt[k - 1] - onCnt[k - 1];
                }
                if(Points[i].y > ymin && Points[i].y < ymax) onCnt[k]++; //不包括上下边界
                if(Points[i].y >= ymin && Points[i].y <= ymax) on2Cnt[k]++; //包括上下边界
            }
            if(k <= 2) return n; //竖线不足两条,那么肯定能包含所有点
            //枚举右边界 j, 如果左边界是 i,答案是 max(leftCnt[j] - leftCnt[i] + on2Cnt[j] + onCnt[i])
            //即让 onCnt[j] - leftCnt[i] 最大
            int val = onCnt[1] - leftCnt[1];
            for(int j = 2; j <= k; ++j) {
                ans = max(ans, on2Cnt[j] + leftCnt[j] + val);
                val = max(val, onCnt[j] - leftCnt[j]);
            }
        }
    return ans;
}

int main() {
    int caseNum = 0;
    while(n = ReadInt(), n) {
        for(int i = 0; i < n; ++i) Points[i].x = ReadInt(), Points[i].y = y[i] = ReadInt();
        printf("Case %d: %d\n", ++caseNum, Solve());
    }
    return 0;
}