Pagini recente » Cod sursa (job #1947055) | Cod sursa (job #2033516) | Cod sursa (job #1669613) | Cod sursa (job #1616619) | Cod sursa (job #2274279)
#include <fstream>
#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(){
ifstream cin("adapost2.in");
ofstream cout("adapost2.out");
cin>>n;
for(int i=1;i<=n;i++){
cin>>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);
double step=maxCoord;
for(int p=1;p<=40;p++){
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;
}
step/=2;
}
cout<<sol.first<<" "<<sol.second;
return 0;
}