kojingharangの日記

SRM 614 Div1 250 MinimumSquare

03:22 |

• 2Dの整数点座標が2〜100個与えられる。整数座標のAABBな正方形のうち点をK個以上含む（辺上は含まない）ものの最小の面積を求めよ。
• 1≦K≦点の個数

• 正方形に含むべき X の範囲 [ X[x0], X[x1] ] を決めて、X座標がその範囲に入ってるY座標を列挙する。
• そのY座標たちをソートして Y 座標の範囲を点が K 個入るように Y[i], Y[i+K-1] と決める。
• そしたら K 個以上含む長方形の幅高さ W, H が出るので max(W, H) が正方形の1辺。
• challengeされる...

あとで

• 何も考えずに当然のように x1 in [x0+1, N) としていた。
• x1 in [x0, N) にしないとK=1の時とかにポシャる。
• くやしけり！

• accepted in practice

class MinimumSquare {
	public:
	long long minArea(vector <int> x, vector <int> y, int K) {
		int N=x.size();
		vector<int> X(x);
		sort(ALL(X));
		ll ans = 1LL<<60;
		//REP(x0, N) RANGE(x1, x0+1, N) { // だめじゃった
		REP(x0, N) RANGE(x1, x0, N) {
			ll W = abs(X[x0]-X[x1])+2;
			VI Y;
			REP(i, N) if(X[x0]<=x[i] && x[i]<=X[x1]) Y.PB(y[i]);
			sort(ALL(Y));
			int M=Y.size();
			REP(i, Y.size()) {
				if(i+K-1>=M) break;
				ll H = abs(Y[i]-Y[i+K-1])+2;
				ans = min(ans, max(W, H));
			}
		}
		return ans*ans;
	}
};

ツイートする