SRM521 Div1 Medium(500) RangeSquaredSubsets

TopCoder

RangeSquaredSubsets

戻り値がlong longだけど、答えがそんなに大きくなることはない。点集合から、その集合のみを含む正方形を求めるのではなく、正方形の位置や大きさを変えて、その正方形が含む点集合を求める。

n-squaredな点集合それぞれに対して、その点集合のみを含む最大で最も左上にある正方形のみを考えるとすると、候補になりうる正方形は、左端がいずれかの点よりちょっと右か、上端が点よりちょっと下か、右端が点上か、下端が点上であり、１辺の長さは2点間のx座標もしくはy座標の差よりちょっと短いか、nhigh。

予め全ての座標を3倍しておいて、位置がちょっと右を+1、長さがちょっと短いを-2とすると、楽。

#include <vector>
#include <set>
#include <algorithm>
using namespace std;

class RangeSquaredSubsets{public:
long long countSubsets( int nlow, int nhigh, vector <int> x, vector <int> y )
{
    int M = (int)x.size();

    //  3倍する
    nlow *= 3,  nhigh *= 3;
    for ( int i=0; i<M; i++ )
        x[i] *= 3,  y[i] *= 3;

    //  n-squaredな点集合
    set<long long> S;

    for ( int px=0; px<M; px++ )
    for ( int fx=0; fx<2; fx++ )    //  0: 左端がx[px]に接する　1: 右端がx[px]を含む
    for ( int py=0; py<M; py++ )
    for ( int fy=0; fy<2; fy++ )    //  0: 上端がy[py]に接する　1: 下端がy[py]を含む
    for ( int pn=0; pn<=M; pn++ )   //  辺の長さの決定に使う点　pn==Mならnhigh
    for ( int fn=0; fn<2; fn++ )    //  0: x軸方向で長さを決める　1: y軸方向
    {
        int n;
        if ( pn<M )
            if ( fn==0 )  n = fx==0 ? x[pn]-x[px]-2 : x[px]-x[pn]-2;
            else          n = fy==0 ? y[pn]-y[py]-2 : y[py]-y[pn]-2;
        else
            n = nhigh;

        if ( nlow<=n && n<=nhigh )
        {
            int ox = fx==0 ? x[px]+1 : x[px]-n;
            int oy = fy==0 ? y[py]+1 : y[py]-n;

            long long s = 0;
            for ( int j=0; j<M; j++ )
                if ( ox<=x[j] && x[j]<=ox+n &&
                     oy<=y[j] && y[j]<=oy+n )
                    s |= 1ll<<j;

            if ( s != 0 )
                S.insert( s );
        }
    }

    return S.size();
}};