描述
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 <stdio.h> #include <cmath> using namespace std; typedef pair<double,double> P; #define rep(i,m,n) for(int i=m;i<=n;i++) #define MAXN 100001 P points[MAXN]; double d(P a,double x){ return pow(pow(a.first-x,2)+pow(a.second,2),0.5); } double get(P a[],int N,double x){ double s=0; rep(i,0,N-1){ s+=d(a[i],x); } return s; } double san(P a[],int N,double l, double r){ double mid1,mid2; while(r>l){ // cout<<l<<":"<<r<<endl; mid1=(r-l)/3+l; mid2=2*(r-l)/3+l; double s1=get(a,N,mid1); double s2=get(a,N,mid2); // cout<<mid1<<","<<mid2<<":"<<s1<<","<<s2<<endl; if(s1<s2) { r=mid2; } else { l=mid1; } if(fabs(mid1-mid2)<0.0000005) break; } return r; } int main(){ int cases;cin>>cases; rep(caseI,1,cases){ int N;cin>>N; double Min=9999999,Max=-999999; rep(i,0,N-1){ cin>>points[i].first>>points[i].second;Min=min(Min,points[i].first);Max=max(Max,points[i].first); } printf("Case %d: %.6lf\n",caseI,san(points,N,Min,Max)); } return 0; } ---------------------------- 总结错误: 自定义的宏(i,1,N)导致下标混乱,稍不留神就会前后不一致( rep(i,1,N) cin>>points[i]...; 后面get(){ rep(i,0,N-1) add(points[i]....} 下次改成rep(i,N) 0->N-1