# POJ2420
三分和二分输出答案是 l 还是 r 就看中间的判断条件,不满足条件更新的那个值就是要输出的值
#include <iostream> | |
#include <cmath> | |
#include <iomanip> | |
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) | |
#define endl '\n' | |
using namespace std; | |
const int N=1e3+100; | |
const double eps=1e-5; | |
int n; | |
int a[N],b[N]; | |
double getdis(double x,double y){ | |
double res=0; | |
for(int i=1;i<=n;i++) res+=sqrt(pow(x-a[i],2)+pow(y-b[i],2)); | |
return res; | |
} | |
double work(double x){ | |
double l=0,r=10000,lmid,rmid; | |
while(r-l>eps){ | |
lmid=l+(r-l)/3; | |
rmid=r-(r-l)/3; | |
if(getdis(x,lmid)>getdis(x,rmid)) l=lmid; | |
else r=rmid; | |
} | |
return getdis(x,lmid); | |
} | |
int main() | |
{ | |
ios; | |
cin>>n; | |
for(int i=1;i<=n;i++) cin>>a[i]>>b[i]; | |
double l=0,r=10000,lmid,rmid; | |
while(r-l>eps){ | |
lmid=l+(r-l)/3; | |
rmid=r-(r-l)/3; | |
if(work(lmid)>work(rmid)) l=lmid; | |
else r=rmid; | |
} | |
cout<<fixed<<setprecision(0)<<work(l)<<endl; | |
return 0; | |
} |