LA 3695 Distant Galaxy（训练指南， 枚举扫描）

算法竞赛训练指南，52页，枚举，线性扫描

本题要点：
1、每个点，先按x坐标排序，
算出单独的y左边有m个，然后遍历 y坐标的上届和下届
for(int a = 0; a < m; ++a) // 下届
{
for(int b = a + 1; b < n; ++b) //上届
{}
}

在上届和下届确定的情况下， 求出一个长方形包含最多的点数

2、几个数组的意义， 数组的坐标指的是，该点的x坐标，排在所有单独坐标的排名， 每一个单独坐标对应一条竖线：

Left[MaxN]	//Left[i] 表示第i条竖线左边有多少点在 ymax上届和下届ymin
on[MaxN]	//on[i] 表示有多少点在第i条竖线上面，而且这些点的 y坐标 满足 ymin < y && ymax > y
on2[MaxN]	//on2[i] 表示有多少点在第i条竖线上面，而且这些点的 y坐标 满足 ymin <= y && ymax => y当确定x坐标的左右边界 i 和 j之后，矩形的点的最大值为 Left[j] - Left[i] +on[i] +on2[j], 遍历取最大值即可

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MaxN = 110;
int y[MaxN], on[MaxN], on2[MaxN], Left[MaxN];
int n;
int m;	// 独立的y坐标struct Point
{
    int x, y;bool operator<(const Point & rhs) const{
    return x < rhs.x;}
}points[MaxN];int solve()
{
    sort(points, points + n);sort(y, y + n);int m = unique(y, y + n) - y;if(m <= 2){
    return n;}int ans = -1;for(int a = 0; a < m; ++a){
    for(int b = a + 1; b < n; ++b){
    int ymin = y[a], ymax = y[b];// 更新当前的 Left[i], on[i], on2[i]int k = 0;	// 单独的 x 坐标for(int i = 0; i < n; ++i){
    if(i == 0 || points[i].x != points[i - 1].x)// 一条新的竖线 {
    ++k;on[k] = on2[k] = 0;Left[k] = k == 0? 0 : Left[k - 1] + on2[k - 1] - on[k - 1];}if(ymin < points[i].y && ymax > points[i].y){
    on[k]++;}if(ymin <= points[i].y && ymax >= points[i].y){
    on2[k]++;}}if(k <= 2){
    return n;}int M = 0;for(int j = 1; j <= k; ++j){
    ans = max(ans, Left[j] + on2[j] + M);M = max(M, on[j] - Left[j]);}}}return ans;
}int main()
{
    int t = 0;while(scanf("%d", &n) != EOF && n){
    for(int i = 0; i < n; ++i){
    scanf("%d%d", &points[i].x, &points[i].y);y[i] = points[i].y;}printf("Case %d: %d\n", ++t, solve());}return 0;
}/* 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 */