Pagini recente » Cod sursa (job #3124245) | Cod sursa (job #2928374) | Cod sursa (job #541423) | Cod sursa (job #1480855) | Cod sursa (job #1083719)
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
int dx[]={-1,0,0,1}; int dy[]={0,-1,1,0};
int n,i,j;
double solx,soly,x[50001],y[50001],nx,ny,best,k,cost;
double dist(double A, double B, double C, double D){
return sqrt((A-C)*(A-C)+(B-D)*(B-D));
}
int main()
{
ifstream f("adapost2.in");
ofstream g("adapost2.out");
f>>n;
for(i=1;i<=n;i++){
f>>x[i]>>y[i];
solx+=x[i];
soly+=y[i];
}
solx=solx/n;
soly=soly/n;
for(i=1;i<=n;i++)
best+=dist(x[i],y[i],solx,soly);
for(k=100;k>0.0001;k=k/2){
for(i=0;i<4;i++){
nx=solx+k*dx[i];
ny=soly+k*dy[i];
cost=0;
for(j=1;j<=n;j++)
cost+=dist(x[j],y[j],nx,ny);
if(cost<best){
best=cost;
solx=nx;
soly=ny;
k*=2;
break;
}
}
}
g<<solx<<" "<<soly<<'\n';
return 0;
}