Codeforces 144 B. Meeting

問題

(xa,ya),(xb,yb)を角とするような、
座標軸に平行なテーブルがある。

このテーブルの辺のうち、座標が整数の点には人がいる。
ストーブがn個あり、それぞれの座標は(x[i],y[i])であり、
ストーブの有効範囲はr[i]である。

どのストーブの有効範囲にもいない人には毛布を配る必要がある。
毛布は何枚必要か、求めよ。

制約条件

座標はすべて整数
座標の絶対値≦1000
r[i]≦1000
n≦1000

方針

人は最大で8000人くらい、ストーブも1000個しかないので、総当りして試す。
C++0xを使って書いてみた。

ラムダ式が微妙に便利。
autoが型推論をもうちょっとしっかりやってくれるといいのだけれど。

ソースコード

#define pb emplace_back
vector<tuple<int,int,int>> v;
vector<tuple<int,int>> g;

int main(){
	int xa,ya,xb,yb,n;
	cin>>xa>>ya>>xb>>yb>>n;
	if(xa>xb)swap(xa,xb);
	if(ya>yb)swap(ya,yb);
	rep(i,2)for(int x=xa;x<xb;x++)g.pb(x+i,i?yb:ya);
	rep(i,2)for(int y=ya;y<yb;y++)g.pb(i?xa:xb,y+i);
	rep(i,n){
		int a,b,c;
		cin>>a>>b>>c;
		v.pb(a,b,c);
	}
	cout<<count_if(all(g),[](tuple<int,int> a){
		return none_of(all(v),[&](tuple<int,int,int> b){
			int x=get<0>(a), y=get<1>(a);
			int X=get<0>(b), Y=get<1>(b), r=get<2>(b);
			return (x-X)*(x-X)+(y-Y)*(y-Y) <= r*r;
		});
	})<<endl;
	return 0;
}