SRM464 Div1 Medium(550) ColorfulDecoration

ColorfulDecoration

二分探索。あるサイズの紙を重ならずに置けるかどうかはバックトラックで探索。

#include <vector>

using namespace std;

class ColorfulDecoration
{
    struct POS
    {
        int x, y;
        POS(int x_, int y_) : x(x_), y(y_) {}
        bool operator==( const POS &p ) const { return x==p.x && y==p.y; }
        bool operator!=( const POS &p ) const { return x!=p.x || y!=p.y; }
    };

    int n;
    POS null;
    vector<POS> pa, pb;
    vector<POS> paper;

    bool check( int size );
    bool BT( int size );
    bool overlap( int size, POS p, vector<POS> paper );

public:
    ColorfulDecoration() : null(-1,-1) {}
    int getMaximum( vector <int> xa, vector <int> ya, vector <int> xb, vector <int> yb );
};

int ColorfulDecoration::getMaximum( vector <int> xa, vector <int> ya, vector <int> xb, vector <int> yb )
{
    n = (int)xa.size();

    null = POS(-1,-1);

    pa.clear();
    pb.clear();
    for ( int i=0; i<n; i++ )
        pa.push_back( POS(xa[i],ya[i]) ),
        pb.push_back( POS(xb[i],yb[i]) );

    int a = 0;
    int b = 1000000001;

    while ( a + 1 < b )
    {
        int c = ( a + b ) / 2;

        if ( check( c ) )
            a = c;
        else
            b = c;
    }

    return a;
}

//  大きさsizeの紙が敷き詰められるか
bool ColorfulDecoration::check( int size )
{
    paper = vector<POS>( n, null );

    //  他と常に重ならない色は予め置いておく
    for ( int i=0; i<n; i++ )
    {
        POS ta = pa[i];  pa[i] = null;
        POS tb = pb[i];  pb[i] = null;

        if ( ! overlap( size, ta, pa )  &&
             ! overlap( size, ta, pb ) )
            paper[i] = ta;

        if ( ! overlap( size, tb, pa )  &&
             ! overlap( size, tb, pb ) )
            paper[i] = tb;

        pa[i] = ta;
        pb[i] = tb;
    }

    return BT( size );
}

//  バックトラック
bool ColorfulDecoration::BT( int size )
{
    //  全ての色を置けたかチェック
    bool f = true;
    for ( int i=0; i<n; i++ )
        if ( paper[i] == null )
            f = false;
    if ( f )
        return true;

    //  どちらにも置けない色があれば終了
    for ( int i=0; i<n; i++ )
    if ( paper[i] == null )
    {
        if ( overlap( size, pa[i], paper )  &&
             overlap( size, pb[i], paper ) )
            return false;
    }

    //  一方にしか置けない色を置く
    for ( int i=0; i<n; i++ )
    if ( paper[i] == null )
    {
        bool fa = overlap( size, pa[i], paper );
        bool fb = overlap( size, pb[i], paper );

        if ( ! fa  &&  fb )
        {
            paper[i] = pa[i];
            bool f = BT( size );
            paper[i] = null;

            return f;
        }

        if ( fa  && ! fb )
        {
            paper[i] = pb[i];
            bool f = BT( size );
            paper[i] = null;

            return f;
        }
    }

    //  両方における色を置く
    for ( int i=0; i<n; i++ )
    if ( paper[i] == null )
    {
        if ( ! overlap( size, pa[i], paper )  &&
             ! overlap( size, pb[i], paper ) )
        {
            paper[i] = pa[i];
            bool f = BT( size );
            paper[i] = null;

            if ( f )
                return true;

            paper[i] = pb[i];
            f = BT( size );
            paper[i] = null;

            if ( f )
                return true;

            return false;
        }
    }
    
    return false;
}

//  大きさsizeの紙をpとpaperの各要素に置いた時に重なるか
bool ColorfulDecoration::overlap( int size, POS p, vector<POS> paper )
{
    for ( int i=0; i<n; i++ )
    if ( paper[i] != null )
        if ( abs( p.x - paper[i].x ) < size  &&
             abs( p.y - paper[i].y ) < size )
            return true;
    
    return false;
}