Cod sursa(job #1967361)

Utilizator TincaMateiTinca Matei TincaMatei Data 16 aprilie 2017 15:35:00
Problema Adapost 2 Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <cstdio>
#include <cmath>

typedef double f64;
const int MAX_N = 50000;
const f64 EPS = 1e-4f;
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 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;
  }
  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;
  while(xdr - xst > EPS) {
    f64 mid = (xdr + xst) / 2.0f;
    y1 = best(mid, n);
    y2 = best(mid + EPS, n);
    f64 delta = sumDist(mid, y1, n) - sumDist(mid + EPS, y2, n);
    if(delta >= 0.0f)
      xst = mid;
    else
      xdr = mid;
  }

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