SRM 421 DIV1 Easy - EquilibriumPoints (復習○)
問題
http://community.topcoder.com/stat?c=problem_statement&pm=10104&rd=13512
直線状に複数の点とその点にある球の数が与えられる。
ある点を考えた時、その点と点ｘの距離をｄ、点ｘの球の数をｍとすると
Ｆ＝Ｇ＊ｍ１＊ｍ２／ｄ＾２で引力が表わされる。
ここでＧは定数。
このとき、引力が左右均衡となる点を求める。
点が複数存在する場合は、昇順に並べる。
解き方
サンプルを見ると各点の間ごとに均衡点があることがわかる。
あとは、その間すべてに対して２分探索すれば答えが求められる。
コード
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class EquilibriumPoints {
public:
double calc(int m,double d){
return m/d/d;
}
vector<double> getPoints(vector<int> x, vector<int> m) {
vector<double> ans;
int n=x.size();
FORE(i,0,n-1){
double low=x[i],high=x[i+1];
FORE(j,0,100){
double mid=(low+high)/2.0;
double cost=0.0;
FORE(k,0,i+1)cost+=calc(m[k],mid-x[k]);
FORE(k,i+1,n)cost-=calc(m[k],mid-x[k]);
if(cost>0)low=mid;
else high=mid;
}
ans.push_back(high);
}
return ans;
}
};
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class EquilibriumPoints {
public:
double calc(int m,double d){
return m/d/d;
}
vector<double> getPoints(vector<int> x, vector<int> m) {
vector<double> ans;
int n=x.size();
FORE(i,0,n-1){
double low=x[i],high=x[i+1];
FORE(j,0,100){
double mid=(low+high)/2.0;
double cost=0.0;
FORE(k,0,i+1)cost+=calc(m[k],mid-x[k]);
FORE(k,i+1,n)cost-=calc(m[k],mid-x[k]);
if(cost>0)low=mid;
else high=mid;
}
ans.push_back(high);
}
return ans;
}
};
