Pagini recente » Diferente pentru planificare/sedinta-20081107 intre reviziile 6 si 28 | Sedinta 2007-11-28 | Istoria paginii problema/heavymetal | deneo | Cod sursa (job #3136648)
//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;
const int dx[4]={1, 0, -1, 0};
const int dy[4]={0, 1, 0, -1};
int k;
for(v=250;v>=0.0001;v*=0.5)
{
for(k=0;k<4;++k)
{
nx=x+dx[k]*v;
ny=y+dy[k]*v;
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;
}