AOJ 0552 - Exposition

コードがやばい．

解法

(x, y) -> (x+y, x-y)という変換(45度回転)をすると，施設iと施設jの距離は
max{|x[i]-x[j]|, |y[i]-y[j]|}
と表されます．以下，変換後の座標系で話をすすめます．
まず，x座標とy座標で幅の広い方(最小値と最大値の差が大きい方．同じときはどちらでもいい)を選び，その座標の最小値と最大値を求める．
この2つが同じテーマだと，どう頑張っても最長になってしまうので違うテーマに分けてあげます．
その後，各テーマで(最小/最大)の(x座標/y座標)をもちながら，次のようにテーマを割り振る．
それぞれのテーマで最も遠い施設を求め，より距離が遠い方(同じときはどちらでもよい)を，他方のテーマに割り当てる．
すべての施設を割り当てたとき，2つのテーマの(x座標/y座標)の最小・最大の差の大きい方が答えになります．

x座標とy座標で幅の広い方，最も遠い点はどう求めたらいいでしょうか．距離の式がx座標，y座標について分離しているので，x座標でソートしたもの，y座標でソートしたものがあるといいですね．さらに，削除がある程度速いといいですね．これって何てstd::set．(なお，特別なデータ構造をつかわなくても解ける模様．)

コード

Ω\・8・)ﾁｭｰﾝ

// ﾅﾆｿﾚｲﾐﾜｶﾝﾅｲ

#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
#include <tuple>

typedef std::pair<int,int> P;
typedef std::tuple<P,bool,int> Q;
std::set<P> setX, setY;
int N;

Q f(int mnX, int mxX, int mnY, int mxY){
    P p = *setX.begin();
    bool isX = true;
    int l = std::max(std::abs(mnX-p.first),
                     std::abs(mxX-p.first));

    P _p;
    int _l;
    _p = *setX.rbegin();
    if((_l = std::max(std::abs(mnX-_p.first),
                      std::abs(mxX-_p.first))) > l){
        p = _p;
        l = _l;
    }

    _p = *setY.begin();
    if((_l = std::max(std::abs(mnY-_p.first),
                      std::abs(mxY-_p.first))) > l){
        p = _p;
        l = _l;
        isX = false;
    }

    _p = *setY.rbegin();
    if((_l = std::max(std::abs(mnY-_p.first),
                      std::abs(mxY-_p.first))) > l){
        p = _p;
        l = _l;
        isX = false;
    }

    return std::make_tuple(p, isX, l);
}

int main(){
    scanf("%d", &N);

    for(int i=0;i<N;i++){
        int x, y;
        scanf("%d %d", &x, &y);

        int x_ = x+y, y_ = x-y;
        setX.insert(std::make_pair(x_, y_));
        setY.insert(std::make_pair(y_, x_));
    }

    int mnX1, mxX1, mnY1, mxY1,
        mnX2, mxX2, mnY2, mxY2;
    if(setX.rbegin()->first-setX.begin()->first >
       setY.rbegin()->first-setY.begin()->first){
        mnX1 = setX.begin()->first;
        mxX1 = mnX1;
        mnY1 = setX.begin()->second;
        mxY1 = mnY1;
        mnX2 = setX.rbegin()->first;
        mxX2 = mnX2;
        mnY2 = setX.rbegin()->second;
        mxY2 = mnY2;

        P p1 = *setX.begin(), p2 = *setX.rbegin();
        setY.erase(std::make_pair(p1.second, p1.first));
        setY.erase(std::make_pair(p2.second, p2.first));
        setX.erase(p1);
        setX.erase(p2);
    }else{
        mnX1 = setY.begin()->second;
        mxX1 = mnX1;
        mnY1 = setY.begin()->first;
        mxY1 = mnY1;
        mnX2 = setY.rbegin()->second;
        mxX2 = mnX2;
        mnY2 = setY.rbegin()->first;
        mxY2 = mnY2;

        P p1 = *setY.begin(), p2 = *setY.rbegin();
        setX.erase(std::make_pair(p1.second, p1.first));
        setX.erase(std::make_pair(p2.second, p2.first));
        setY.erase(p1);
        setY.erase(p2);
    }
    
    for(;!setX.empty();){
        Q q1 = f(mnX1, mxX1, mnY1, mxY1),
          q2 = f(mnX2, mxX2, mnY2, mxY2);

        if(std::get<2>(q1) > std::get<2>(q2)){
            mnX2 = std::min(mnX2, std::get<1>(q1) ? std::get<0>(q1).first : std::get<0>(q1).second);
            mxX2 = std::max(mxX2, std::get<1>(q1) ? std::get<0>(q1).first : std::get<0>(q1).second);
            mnY2 = std::min(mnY2, std::get<1>(q1) ? std::get<0>(q1).second : std::get<0>(q1).first);
            mxY2 = std::max(mxY2, std::get<1>(q1) ? std::get<0>(q1).second : std::get<0>(q1).first);

            setX.erase(std::get<1>(q1) ? std::get<0>(q1) : std::make_pair(std::get<0>(q1).second, std::get<0>(q1).first));
            setY.erase(std::get<1>(q1) ? std::make_pair(std::get<0>(q1).second, std::get<0>(q1).first) : std::get<0>(q1));
        }else{
            mnX1 = std::min(mnX1, std::get<1>(q2) ? std::get<0>(q2).first : std::get<0>(q2).second);
            mxX1 = std::max(mxX1, std::get<1>(q2) ? std::get<0>(q2).first : std::get<0>(q2).second);
            mnY1 = std::min(mnY1, std::get<1>(q2) ? std::get<0>(q2).second : std::get<0>(q2).first);
            mxY1 = std::max(mxY1, std::get<1>(q2) ? std::get<0>(q2).second : std::get<0>(q2).first);

            setX.erase(std::get<1>(q2) ? std::get<0>(q2) : std::make_pair(std::get<0>(q2).second, std::get<0>(q2).first));
            setY.erase(std::get<1>(q2) ? std::make_pair(std::get<0>(q2).second, std::get<0>(q2).first) : std::get<0>(q2));
        }
        
    printf("%d\n", std::max({mxX1-mnX1, mxY1-mnY1,
                    mxX2-mnX2, mxY2-mnY2}));
}