Cod sursa(job #2110577)

Utilizator cella.florescuCella Florescu cella.florescu Data 20 ianuarie 2018 21:27:32
Problema Adapost 2 Scor 77
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5e4;

double x[MAXN], y[MAXN];

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

int dirx[] = {-1, 0, 1, 1, 1, -1}, diry[] = {0, 1, 1, 0, -1, -1, -1};

int main()
{
    int n;
    ifstream fin("adapost2.in");
    fin >> n;
    double xp = 0.0, yp = 0.0;
    for (int i = 0; i < n; ++i) {
      fin >> x[i] >> y[i];
      xp += x[i]; yp += y[i];
    }
    fin.close();
    xp /= n; yp /= n;
    double mv = 250;
    for (int step = 0; step < (n <= 1000 ? 40 : 23); ++step) {
      int dir;
      double minD = 1e10;
      for (int d = 0; d < 8; ++d) {
        double dst = 0.0;
        for (int i = 0; i < n; ++i)
          dst += dist(xp + mv * dirx[d], yp + mv * diry[d], x[i], y[i]);
        if (dst < minD) {
          minD = dst;
          dir = d;
        }
      }
      xp += mv * dirx[dir]; yp += mv * diry[dir];
      mv *= 0.55;
    }
    ofstream fout("adapost2.out");
    fout << setprecision(4) << fixed << xp << " " << yp;
    fout.close();
    return 0;
}