Mai intai trebuie sa te autentifici.
Cod sursa(job #1564512)
Utilizator | Data | 9 ianuarie 2016 18:52:05 | |
---|---|---|---|
Problema | Adapost 2 | Scor | 75 |
Compilator | c | Status | done |
Runda | Arhiva de probleme | Marime | 0.98 kb |
#include <stdio.h>
#include <math.h>
#define MAXN 50000
int l[MAXN], c[MAXN];
int d[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
inline double dist(long long x, long long y, int n){
int i;
double d = 0;
for(i = 0; i < n; i++){
d += sqrt((x - l[i]) * (x - l[i]) + (y - c[i]) * (y - c[i]));
}
return d;
}
int main(){
FILE *in = fopen("adapost2.in", "r");
int n, i;
double a, b;
long long x = 0, y = 0, pas;
fscanf(in, "%d", &n);
for(i = 0; i < n; i++){
fscanf(in, "%lf%lf", &a, &b);
l[i] = a * 10000;
c[i] = b * 10000;
x += l[i]; y += c[i];
}
x /= n; y /= n;
pas = (1 << 20);
while(pas > 0){
for(i = 0; i < 4; i++){
while(dist(x + d[i][0] * pas, y + d[i][1] * pas, n) < dist(x, y, n)){
x += d[i][0] * pas;
y += d[i][1] * pas;
}
}
pas /= 2;
}
FILE *out = fopen("adapost2.out", "w");
fprintf(out, "%.4lf %.4lf", x / 10000.0, y / 10000.0);
fclose(out);
return 0;
}