Pagini recente » Cod sursa (job #1386716) | Cod sursa (job #2853672) | Cod sursa (job #3125560) | Cod sursa (job #760159) | Cod sursa (job #2274283)
#include <cstdio>
#include <utility>
#include <cmath>
#define Point pair<double,double>
using namespace std;
const int maxN=5e4+3;
const int maxCoord=1e3;
const double EPS=1e-4;
const int dx[]={-1,0,1,0};
const int dy[]={0,1,0,-1};
int n;
Point v[maxN];
Point centroid,sol;
double getDist(Point a,Point b){
double difx=a.first-b.first;
double dify=a.second-b.second;
return sqrt(difx*difx+dify*dify);
}
double getTotalDist(Point center){
double res=0;
for(int i=1;i<=n;i++)
res+=getDist(center,v[i]);
return res;
}
int main(){
freopen("adapost2.in","r",stdin);
freopen("adapost2.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lf %lf",&v[i].first,&v[i].second);
centroid.first+=v[i].first;
centroid.second+=v[i].second;
}
centroid.first/=n;
centroid.second/=n;
sol=centroid;
double bestDist=getTotalDist(sol);
for(double step=maxCoord;step>EPS;){
Point cand;
double minDist=1e10;
for(int i=0;i<4;i++){
Point curr;
curr.first=sol.first+step*dx[i];
curr.second=sol.second+step*dy[i];
double currentDist=getTotalDist(curr);
if(currentDist<minDist){
minDist=currentDist;
cand=curr;
}
}
if(minDist<bestDist){
bestDist=minDist;
sol=cand;
} else {
step/=2;
}
}
printf("%.5lf %.5lf",sol.first,sol.second);
return 0;
}