問題
http://community.topcoder.com/stat?c=problem_statement&pm=10512&rd=13899
解き方
元となる点はすべて座標上の点なので、
すべての実数上の点を調べなくても、0.5単位ですべての位置を調べればよい。
コード
class TheNewHouseDivOne {
public: double distance(vector<int> x, vector<int> y, int k) {
double ret=1e+9;
int n=x.size();
for(double xx=-100;xx<=100;xx+=0.5)for(double yy=-100;yy<=100;yy+=0.5){
vector<double> vx;
FORE(i,0,n)vx.push_back(abs(xx-x[i])+abs(yy-y[i]));
sort(all(vx));
ret=min(ret,vx[k-1]);
}
return ret;
}
};
public: double distance(vector<int> x, vector<int> y, int k) {
double ret=1e+9;
int n=x.size();
for(double xx=-100;xx<=100;xx+=0.5)for(double yy=-100;yy<=100;yy+=0.5){
vector<double> vx;
FORE(i,0,n)vx.push_back(abs(xx-x[i])+abs(yy-y[i]));
sort(all(vx));
ret=min(ret,vx[k-1]);
}
return ret;
}
};