Mai intai trebuie sa te autentifici.

Cod sursa(job #1564512)

Utilizator hrazvanHarsan Razvan hrazvan 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;
}