Pagini recente » Cod sursa (job #2723679) | Cod sursa (job #858855) | Cod sursa (job #2349115) | Cod sursa (job #2713310) | Cod sursa (job #63756)
Cod sursa(job #63756)
#include <cstdio>
#include <cmath>
#include <cstdlib>
#define dim 50001
int N;
double X[dim], Y[dim];
double d(double xa, double ya, double xb, double yb)
{
return
sqrt( (xa-xb)*(xa-xb) + (ya-yb)*(ya-yb) );
}
double suma(double x, double y)
{
int i;
double ret = 0;
for(i=1; i<=N; ++i)
ret += d(x, y, X[i], Y[i]);
return ret;
}
int main()
{
freopen("adapost2.in", "rt", stdin);
freopen("adapost2.out", "wt", stdout);
scanf("%d", &N);
int i;
double x, y, nx, ny, aprox, min, mi, s, xf, yf, maxx, minx, maxy, miny;
maxx = maxy = 0;
for(i=1; i<=N; ++i)
{
scanf("%lf %lf", X+i, Y+i);
if(X[i] < minx) minx = X[i];
if(X[i] > maxx) maxx = X[i];
if(Y[i] < miny) miny = Y[i];
if(Y[i] > maxy) maxy = Y[i];
}
// x = rand() % 1000;
// y = rand() % 1000;
x = (maxx + minx) / 2;
y = (maxy + miny) / 2;
min = suma(x, y);
for(aprox=1; aprox>=0.0001; aprox/=10)
{
do
{
mi = min;
nx = x + aprox;
ny = y;
s = suma(nx, ny);
if(s < min)
{
min = s;
xf = nx;
yf = ny;
}
nx = x - aprox;
ny = y;
s = suma(nx, ny);
if(s < min)
{
min = s;
xf = nx;
yf = ny;
}
nx = x;
ny = y + aprox;
s = suma(nx, ny);
if(s < min)
{
min = s;
xf = nx;
yf = ny;
}
nx = x;
ny = yf - aprox;
s = suma(nx, ny);
if(s < min)
{
min = s;
xf = nx;
yf = ny;
}
if(min < mi)
x = xf, y = yf;
} while(min < mi);
x = xf;
y = yf;
}
printf("%.4lf %.4lf", x, y);
fclose(stdin);
fclose(stdout);
return 0;
}