TopCoder SRM 614 Div1 Easy MinimumSquare [1人競技プログラミング Advent Calendar 2016 14日目]

この記事は1人競技プログラミング Advent Calendar 2016 14日目の記事です。

問題概要：
TopCoder Statistics - Problem Statement
N(1<=N<=100)個の点のX座標とY座標が与えられる。(-1,000,000,000 <= x[i],y[i] <= 1,000,000,000)
K個(1<=K<=N)の点を含み、軸に平行で四隅の点の座標が整数である正四角形の最小の面積を求めよ。

解いた方法：
最初、ある1点を四隅に決め打ちして残りのもう1点を探索し、内包する点の数を数えればいいかと思ったらコーナーケースを見つけて断念。(十字に4点が置かれているケース)
K=1,K=2,K=3,それ以外の4つのケースで場合分けして計算。
・K=1のとき
適当などっかの点が含まれていればいいので4を返す。

・K=2のとき
2つの点を全探索して最小の面積を探す。

・K=3のとき
3つの点を全探索して最小の面積を探す。

・K<=4のとき
4点決め打ちしてその中にある点の数を数える。
こうすれば十字のケースの際をカバーできる。
O(NC4*N)で約4000万となり、頑張れば通る。(実際には1.4秒ぐらいのケースが最大だったっぽい)

#include<bits/stdc++.h>

#define MP make_pair
#define PB push_back
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<(n);i++)
#define REP1(i,n) for(int i=1;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
#define RREP(i,n) for(int i=(n);i>=0;i--)
#define CLR(a)      memset((a),0,sizeof(a))
#define MCLR(a)     memset((a),-1,sizeof(a))
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef pair<int,int> PII;

const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;

const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};

class MinimumSquare {
    public:
    vector<int> x;
    vector<int> y;
    int K;
    LL minArea(vector<int> _xx, vector<int> _yy, int _KK) {
        x = _xx, y = _yy, K = _KK;

        LL ans,minx,miny,maxx,maxy,xx,yy,ss;
        ans = INFL;

        if(K == 1) return 4;
        if(K == 2){
            REP(i, x.size()){
                REP2(j, i+1, x.size()){
                    xx = max(x[i],x[j]) - min(x[i],x[j]);
                    yy = max(y[i],y[j]) - min(y[i],y[j]);
                    ss = max(abs(xx), abs(yy)) + 2;
                    ans = min(ans, ss*ss);
                }
            }
        }else if(K == 3){
            REP(i, x.size()){
                REP2(j, i+1, x.size()){
                    REP2(k, j+1, x.size()){
                        xx = max(max(x[i],x[j]),x[k]) - min(min(x[i],x[j]),x[k]);
                        yy = max(max(y[i],y[j]),y[k]) - min(min(y[i],y[j]),y[k]);
                        ss = max(abs(xx), abs(yy)) + 2;
                        ans = min(ans, ss*ss);
                    }
                }
            }
        }else{
            REP(i, x.size()){
                REP2(j, i+1, x.size()){
                    REP2(k, j+1, x.size()){
                        REP2(l, k+1, x.size()){
                            maxx = max(max(x[i],x[j]),max(x[k],x[l]));
                            minx = min(min(x[i],x[j]),min(x[k],x[l]));
                            maxy = max(max(y[i],y[j]),max(y[k],y[l]));
                            miny = min(min(y[i],y[j]),min(y[k],y[l]));
                            ss = max(abs(maxx-minx), abs(maxy-miny)) + 2;

                            int cnt = 0;
                            REP(m, x.size()){
                                cnt += (minx <= x[m] && x[m] <= maxx && miny <= y[m] && y[m] <= maxy);
                            }
                            if(K <= cnt){
                                ans = min(ans, ss*ss);
                            }
                        }
                    }
                }
            }
        }

        return ans;
    }
};