Pagini recente » Cod sursa (job #2735630) | Cod sursa (job #2619838) | Cod sursa (job #1099779) | Cod sursa (job #2654206) | Cod sursa (job #328952)
Cod sursa(job #328952)
#include <stdio.h>
#include <math.h>
#define dim 50001
#define eps 0.00001
int n;
double x[dim], y[dim], xs, ys;
double calc_dist(double xx, double yy) {
double dist=0.0;
int i;
for (i=1; i<=n; ++i)
dist+=sqrt((xx-x[i])*(xx-x[i])+(yy-y[i])*(yy-y[i]));
return dist;
}
void simulated_annealing() {
const int dx[]={0, 1, 0, -1}, dy[]={1, 0, -1, 0};
int i, ok;
double xt, yt, offset=1000.0, dist;
xs=ys=0;
/*for (i=1; i<=n; ++i) xs+=x[i], ys+=y[i];
xs/=n, ys/=n;*/
dist=calc_dist(xs, ys);
while (offset>eps) {
ok=1;
while (ok) {
ok=0;
for (i=0; i<=3; ++i) {
xt=xs+offset*(double)dx[i];
yt=ys+offset*(double)dy[i];
if (calc_dist(xt, yt)<dist) {
dist=calc_dist(xt, yt);
xs=xt, ys=yt;
ok=1;
}
}
}
offset/=10;
}
}
int main() {
int i;
freopen("adapost2.in", "r", stdin);
freopen("adapost2.out", "w", stdout);
scanf("%d\n", &n);
for (i=1; i<=n; ++i) scanf("%lf %lf\n", &x[i], &y[i]);
simulated_annealing();
printf("%.4lf %.4lf\n", xs, ys);
return 0;
}