UVa 1382 - Distant Galaxy | Sengxian's Blog

UVa 1382 - Distant Galaxy

#思维 #扫描法

Published on 2016-02-02

描述

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

样例输入

样例输出

Case 1: 7

分析

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

UVa 11054 - Wine trading in Gergovia UVa 812 - Trade on Verweggistan