A 市是一个高度规划的城市,可是科技高端发达的地方,居民们也不能忘记运动和锻炼,因此城市规划局在设计 A 市的时候也要考虑为居民们建造一个活动中心,方便居住在 A 市的居民们能随时开展运动,锻炼强健的身心。
城市规划局希望活动中心的位置满足下面条件:
1. 到全部居住地的总距离最小。
2. 为了方便活动中心的资源补给和其它器材的维护,活动中心必须建设在 A 市的主干道上。
为了简化问题。我们将 A 市摆在二维平面上,城市的主干道看作直角坐标系平的 X 轴。城市中全部的居住地都能够看成二维平面上的一个点。
如今,A 市的城市规划局希望知道活动中心建在哪儿最好。
第一行包含一个数 T,表示数据的组数。
接下来包括 T 组数据,每组数据的第一行包括一个整数 N,表示 A 市共同拥有 N 处居住地
接下来 N 行表示每处居住地的坐标。
对于每组数据,输出一行 "Case X: Y",当中 X 表示每组数据的编号 (从 1 開始),Y 表示活动中心的最优建造位置。我们建议你的输出保留 Y 到小数点后 6 位或以上。不论什么与标准答案的绝对误差或者相对误差在 10-6 以内的结果都将被视为正确。
小数据:1 ≤ T ≤ 1000, 1 ≤ N ≤ 10
大数据:1 ≤ T ≤ 10, 1 ≤ N ≤ 105
对于全部数据,坐标值都是整数且绝对值都不超过 106
例子 1:活动中心的最优建造位置为 (1.678787, 0)
例子输入
- 1
- 3
- 1 1
- 2 2
- 3 3
例子输出
- Case 1: 1.678787
之后採用二分法求解
- #include<iostream>
- #include<algorithm>
- #include<cstring>
- #include<cstdio>
- #include<string>
- #include<cmath>
- using namespace std;
- vector<pair<double,double>> point;
- const double EPS=0.0000000001;
- bool operator < (const pair<double ,double > &lhs,const pair<double,double> &rhs)
- {
- return lhs.first<rhs.first;
- }
- bool Check(double x)
- {
- double sum=0;
- int len=point.size();
- double a,b;
- for(int i=0;i<len;i++)
- {
- a=x-point[i].first;
- b=sqrt(a*a+(point[i].second*point[i].second));
- sum+=a/b;
- }
- return sum>=0;
- }
- int main()
- {
- int icase;
- while(cin>>icase)
- {
- for(int c=1;c<=icase;c++)
- {
- int ic;
- cin>>ic;
- point.clear();
- while(ic--)
- {
- cin>>pt.first>>pt.second;
- point.push_back(pt);
- }
- sort(point.begin(),point.end());
- double l=point[0].first;
- double h=point[point.size()-1].first;
- while(fabs(l-h)>=EPS)
- {
- double mid=(l+h)/2;
- if(Check(mid))
- {
- h=mid;
- }
- else
- {
- l=mid;
- }
- }
- printf("Case %d: %.6lf\n",i,mid);
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2049125.html