Pagini recente » Diferente pentru preoni-2005/runda-2/solutii intre reviziile 21 si 24 | Statistici Zethpix (Zethpix) | Cod sursa (job #3294966) | Cod sursa (job #3175220) | Cod sursa (job #3136647)
//Ilie Dumitru
#include<cstdio>
#include<cmath>
const int NMAX=50005;
struct pos
{
double x, y;
};
int N;
pos v[NMAX];
inline double getDist(pos a, pos b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double getTotalDistance(pos p)
{
int i;
double d=0;
for(i=0;i<N;++i)
d+=getDist(p, v[i]);
return d;
}
pos getBest()
{
double x=500, y=500, nx, ny;
double v;
double currDist=getTotalDistance({x, y}), aux;
for(v=250;v>=0.0001;v*=0.5)
{
nx=x;
ny=y+v;
aux=getTotalDistance({nx, ny});
if(aux<currDist)
{
currDist=aux;
x=nx;
y=ny;
}
else
{
nx=x;
ny=y-v;
aux=getTotalDistance({nx, ny});
if(aux<currDist)
{
currDist=aux;
x=nx;
y=ny;
}
}
nx=x+v;
ny=y;
aux=getTotalDistance({nx, ny});
if(aux<currDist)
{
currDist=aux;
x=nx;
y=ny;
}
else
{
nx=x-v;
ny=y;
aux=getTotalDistance({nx, ny});
if(aux<currDist)
{
currDist=aux;
x=nx;
y=ny;
}
}
}
return {x, y};
}
int main()
{
FILE* f=fopen("adapost2.in", "r"), *g=fopen("adapost2.out", "w");
int i;
pos ans;
fscanf(f, "%d", &N);
for(i=0;i<N;++i)
fscanf(f, "%lf%lf", &v[i].x, &v[i].y);
ans=getBest();
fprintf(g, "%.6lf %.6lf\n", ans.x, ans.y);
fclose(f);
fclose(g);
return 0;
}