SRM521 Div2 Hard(1000) SquaredSubsets

SquaredSubsets

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

n-squaredな点集合それぞれに対して、その点集合のみを含む最も左上にある正方形のみを考えるとすると、候補になりうる正方形は、左端がいずれかの点よりちょっと右か、上端が点よりちょっと下か、右端が点上か、下端が点上。

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

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

class SquaredSubsets{public:
long long countSubsets( int n, vector <int> x, vector <int> y )
{
    int N = (int)x.size();

    //  2倍する
    n *= 2;
    for ( int i=0; i<N; i++ )
        x[i] *= 2,  y[i] *= 2;

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

    for ( int px=0; px<N; px++ )
    for ( int fx=0; fx<2; fx++ )    //  0: 左端がx[px]に接する　1: 右端がx[px]を含む
    for ( int py=0; py<N; py++ )
    for ( int fy=0; fy<2; fy++ )    //  0: 上端がy[py]に接する　1: 下端がy[py]を含む
    {
        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 i=0; i<N; i++ )
            if ( ox<=x[i] && x[i]<=ox+n &&
                 oy<=y[i] && y[i]<=oy+n )
                s |= 1ll<<i;
        if ( s!=0 )
            S.insert( s );
    }

    return S.size();
}};