問題
http://community.topcoder.com/stat?c=problem_statement&pm=10731&rd=14181
長方形を、与えられた赤と青の円で覆いたい。
各円について、その直径が与えられる。
また、円の中心は長方形を横１線に分割する線上にあるようにする。
また円が重複するとき、前の円とは違う色にしなければならない。
このとき、すべて覆うのに必要な最小の円の数を求める。
ただし、そのような場合がないときは−１を返す。
解き方
赤と青それぞれの円に対し降順にソートし、
赤から覆い始める場合、青から覆い始める場合それぞれについて
いくつの円で覆えるか確かめてあげればよい。
コード
class ColoringRectangle {
public:
int calc(vector<int> a,vector<int> b,int w,double h){
double sum=0;
int at=0,ret=0;
while(1){
if(at>=a.size()||a[at]/2.0<h)break;
sum+=sqrt(a[at]*a[at]/4.0-h*h)*2;
ret++;
if(sum>=w)return ret;
if(at>=b.size()||b[at]/2.0<h)break;
sum+=sqrt(b[at]*b[at]/4.0-h*h)*2;
ret++;
if(sum>=w)return ret;
at++;
}
return 1e+9;
}
int chooseDisks(int width, int height, vector<int> red, vector<int> blue) {
sort(red.rbegin(),red.rend());
sort(blue.rbegin(),blue.rend());
int ret=1e+9;
ret=min(ret,calc(red,blue,width,height/2.0));
ret=min(ret,calc(blue,red,width,height/2.0));
return ret==1e+9 ? -1 : ret;
}
};
public:
int calc(vector<int> a,vector<int> b,int w,double h){
double sum=0;
int at=0,ret=0;
while(1){
if(at>=a.size()||a[at]/2.0<h)break;
sum+=sqrt(a[at]*a[at]/4.0-h*h)*2;
ret++;
if(sum>=w)return ret;
if(at>=b.size()||b[at]/2.0<h)break;
sum+=sqrt(b[at]*b[at]/4.0-h*h)*2;
ret++;
if(sum>=w)return ret;
at++;
}
return 1e+9;
}
int chooseDisks(int width, int height, vector<int> red, vector<int> blue) {
sort(red.rbegin(),red.rend());
sort(blue.rbegin(),blue.rend());
int ret=1e+9;
ret=min(ret,calc(red,blue,width,height/2.0));
ret=min(ret,calc(blue,red,width,height/2.0));
return ret==1e+9 ? -1 : ret;
}
};