Codeforces #330 Div1 C. Edo and Magnets

Bよりこっちの方が簡単？
http://codeforces.com/contest/594/problem/C

問題

N個の軸に平行な辺をもつ矩形が与えられる。

ここで、１つの軸に平行な辺をもち、かつ辺の長さが整数の矩形を考える。
この矩形が、元の矩形の中点のうち(N-K)個以上を含む(または外周に乗る)ようにしたい。
そのような矩形の最小面積を求めよ。

解法

N個の矩形については、欲しい情報は中点だけなのでさっさと中点を計算しよう。
奇数を2で割ると非整数になって面倒なので、座標全体を2倍にしておくと楽である。

あとはKは比較的小さいため、頂点をX座標順及びY座標順にソートしたsetを持っておき、左・右・上・下から合計K個取り除くケースを総当たりし、残った点を含む最小矩形を求めればよい。

int N,K;
int X[202020],Y[202020];
set<pair<int,int> > SX,SY;
vector<int> rem;

void del(int x) {
	rem.push_back(x);
	SY.erase({Y[x],x});
	SX.erase({X[x],x});
}

void solve() {
	int i,j,k,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) {
		int x1,y1,x2,y2;
		cin>>x1>>y1>>x2>>y2;
		X[i]=(x1+x2);
		Y[i]=(y1+y2);
		SX.insert({X[i],i});
		SY.insert({Y[i],i});
	}
	
	ll mi=1LL<<61;
	int l,r,t,b;
	for(l=0;l<=K;l++) for(r=0;l+r<=K;r++) for(t=0;l+r+t<=K;t++) {
		b=K-l-r-t;
		rem.clear();
		FOR(i,l) del(SX.begin()->second);
		FOR(i,r) del(SX.rbegin()->second);
		FOR(i,t) del(SY.begin()->second);
		FOR(i,b) del(SY.rbegin()->second);
		
		ll w = SX.rbegin()->first-SX.begin()->first;
		w = (w+1)/2;
		if(w<=0) w=1;
		ll h = SY.rbegin()->first-SY.begin()->first;
		h = (h+1)/2;
		if(h<=0) h=1;
		
		mi =min(mi,w*h);
		
		FORR(r,rem) {
			SX.insert({X[r],r});
			SY.insert({Y[r],r});
		}
	}
	cout<<mi<<endl;
	
}

まとめ

これ矩形の中点をマグネットで止めるって設定必要だったのかな。
最初からマグネットの座標だけ与えてくれればいいんじゃ…。