Pagini recente » Cod sursa (job #722458) | Cod sursa (job #2445278) | Cod sursa (job #2425133) | Cod sursa (job #462828) | Cod sursa (job #4003)
Cod sursa(job #4003)
#include <stdio.h>
#include <math.h>
struct point {double x, y;};
int N, i, j;
point v[50100];
point X;
double di[] = {-1, 0, 1, 0, -1, 1, 1, -1};
double dj[] = {0, 1, 0 , -1, 1, 1, -1, -1};
point apropie(point XX, double dist) {
double best = -1;
int i, p= -1 ;
best = 0;
for (i=0; i<N; i++){
double d1 = XX.x - v[i].x, d2 = XX.y - v[i].y;
best+=sqrt(d1*d1+d2*d2);
}
// best = -1;
for (int d =0; d<4; d++) {
point Y = XX;
Y.x+=di[d]*dist;
Y.y+=dj[d]*dist;
double A = 0;
for (i=0; i<N; i++){
double d1 = Y.x - v[i].x, d2 = Y.y - v[i].y;
A+=sqrt(d1*d1+d2*d2);
}
if (best==-1 || A < best) {best = A; p = d;}
}
if (p!=-1){
XX.x+=di[p]*dist;
XX.y+=dj[p]*dist;}
return XX;
}
int main() {
freopen("adapost2.in", "r", stdin);
freopen("adapost2.out", "w", stdout);
scanf("%d", &N);
for (i=0; i<N; i++) scanf("%lf %lf", &(v[i].x), &(v[i].y));
for (i=0; i<N; i++) X.x+=v[i].x, X.y+=v[i].y;
// printf("%lf %lf\n", X.x, X.y);
X.x/=1./N ;
X.y/=1./N;
double dist = 4000;
for (int k = 1; k<=100; k++) {
dist = dist/2.0;
for (int j = 1; j<=8; j++)
X = apropie(X, dist);
}
printf("%lf %lf\n", X.x, X.y);
return 0;
}