Cod sursa(job #1967363)

Utilizator TincaMateiTinca Matei TincaMatei Data 16 aprilie 2017 15:37:38
Problema Adapost 2 Scor 64
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <cstdio>
#include <cmath>

typedef double f64;
const int MAX_N = 50000;
const f64 EPS = 1e-3f;
f64 x[MAX_N], y[MAX_N];

inline f64 dist(f64 x1, f64 y1, f64 x2, f64 y2) {
  return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

inline f64 sumDist(f64 x1, f64 y1, int n) {
  f64 s = 0.0f;
  for(int i = 0; i < n; ++i)
    s = s + dist(x1, y1, x[i], y[i]);
  return s;
}

inline f64 best(f64 xRez, int n, f64 &sum) {
  f64 yst = 0.0f, ydr = 1000.0f + EPS;
  while(ydr - yst > EPS) {
    f64 mid = (yst + ydr) / 2.0f;
    f64 delta = sumDist(xRez, mid, n) - sumDist(xRez, mid + EPS, n);
    if(delta >= 0.0f)
      yst = mid;
    else
      ydr = mid;
  }
  sum = sumDist(xRez, yst, n);
  return yst;
}

int main() {
  int n;
  FILE *fin = fopen("adapost2.in", "r");
  fscanf(fin, "%d", &n);
  for(int i = 0; i < n; ++i)
    fscanf(fin, "%lf%lf", &x[i], &y[i]);
  fclose(fin);

  f64 xst = 0.0f, xdr = 1000.0f + EPS, y1, y2, s1, s2;
  while(xdr - xst > EPS) {
    f64 mid = (xdr + xst) / 2.0f;
    best(mid, n, s1);
    best(mid + EPS, n, s2);
    f64 delta = s1 - s2;
    if(delta >= 0.0f)
      xst = mid;
    else
      xdr = mid;
  }

  FILE *fout = fopen("adapost2.out", "w");
  fprintf(fout, "%.3f %.3f", xst, best(xst, n, s1));
  fclose(fout);
  return 0;
}