Cod sursa(job #1968346)

Utilizator TincaMateiTinca Matei TincaMatei Data 17 aprilie 2017 17:14:14
Problema Adapost 2 Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <cstdio>
#include <cmath>
//retard trying to learn gradient descent
typedef double f64;
const int MAX_N = 50000;
const f64 EPS = 1e-5f;
const f64 GAMMA = 2.0f;
const f64 PREC = 1e-5f;
const int ITER = 100;
f64 x[MAX_N], y[MAX_N];

inline f64 calc(f64 xP, f64 yP, int n) {
  f64 s = 0.0f;
  for(int i = 0; i < n; ++i)
    s = s + sqrt((xP - x[i]) * (xP - x[i]) + (yP - y[i]) * (yP - y[i]));
  return s;
}

int main() {
  int n, iter;
  f64 xr, yr, xpr, ypr, step;
  xr = 0.0f;
  yr = 0.0f;
  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]);
    xr = xr + x[i];
    yr = yr + y[i];
  }

  fclose(fin);
  xr = xr / n;
  yr = yr / n;
  iter = ITER;
  do {
    xpr = xr;
    ypr = yr;
    f64 deltax = (calc(xpr + EPS, ypr, n) - calc(xpr, ypr, n)) / EPS;
    f64 deltay = (calc(xpr, ypr + EPS, n) - calc(xpr, ypr, n)) / EPS;
    xr += -GAMMA * deltax;
    yr += -GAMMA * deltay;
    step = GAMMA * sqrt((xr - xpr) * (xr - xpr) + (yr - ypr) * (yr - ypr));
  } while(fabs(step) > PREC);

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