2014年12月16日 星期二

2014/12/16 ACM-ICPC Live Archive 3695 - Distant Galaxy

/*
    O(N^3)
*/
/* https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1696 */
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>
#include <map>

using namespace std;

typedef vector<int>::iterator vit;
vector<int> x, y;

map<int, int> m;

int N;
int X[200], Y[200];

void process()
{
    sort(x.begin(), x.end());
    sort(y.begin(), y.end());

    vit it;
    it = unique(x.begin(), x.end());
    x.resize(it-x.begin());

    it = unique(y.begin(), y.end());
    y.resize(it-y.begin());

    m.clear();
    for(int xi = 0; xi < x.size(); xi++)
        m[x[xi] ] = xi+1;
    for(int Ni = 0; Ni < N; Ni++)
        X[Ni] = m[X[Ni] ];

    m.clear();
    for(int yi = 0; yi < y.size(); yi++)
        m[y[yi] ] = yi+1;
    for(int Ni = 0; Ni < N; Ni++)
        Y[Ni] = m[Y[Ni] ];
}

int A[200], B[200];

int Ti = 0;

int main()
{
    while(1)
    {
        scanf("%d", &N);
        if( !N ) break;

        int Ans = 0;

        x.clear();
        y.clear();

        for(int Ni = 0; Ni < N; Ni++)
        {
            scanf("%d %d", &X[Ni], &Y[Ni]);
            x.push_back(X[Ni]);
            y.push_back(Y[Ni]);
        }

        process();

        for(int xi = 0; xi <= x.size(); xi++)
            for(int xj = xi; xj <= x.size(); xj++)
            {
                fill(A, A+200, 0);
                fill(B, B+200, 0);

                for(int Ni = 0; Ni < N; Ni++)
                {
                    if( X[Ni] == xi || X[Ni] == xj )
                        A[Y[Ni] ]++;

                    if( xi < X[Ni] && X[Ni] < xj ) B[Y[Ni] ]++;
                }


                for(int yi = 1; yi <= y.size(); yi++)
                    A[yi] += A[yi-1];

                int mn = 0;

                for(int yi = 1; yi <= y.size(); yi++)
                {
                    Ans = max(Ans, A[yi]+B[yi]-mn);
                    mn = min(mn, A[yi-1]-B[yi]);
                }
            }

        printf("Case %d: %d\n", ++Ti, Ans);
    }
}

沒有留言:

張貼留言