Cod sursa(job #2110606)

Utilizator cella.florescuCella Florescu cella.florescu Data 20 ianuarie 2018 22:06:26
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.28 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5e4;
const double CT = sqrt(3) / 2;

double x[MAXN], y[MAXN];
double dirx[] = {0, CT, CT, 0, -CT, -CT}, diry[] = {1, 0.5, -0.5, -1, -0.5, 0.5, };

class InputReader {
  private:
    FILE *fin;
    static const int BUFF_SIZE = 1 << 17;
    int bp;
    char buff[BUFF_SIZE];
    inline void next_char() {
      if (++bp == BUFF_SIZE) {
        fread(buff, sizeof(char), BUFF_SIZE, fin);
        bp = 0;
      }
    }
  public:
    InputReader (const char* file) {
      fin = fopen(file, "r");
      bp = BUFF_SIZE - 1;
    }
    InputReader& operator >> (int &num) {
      num = 0;
      while (isdigit(buff[bp]) == 0)
        next_char();
      while (isdigit(buff[bp])) {
        num = num * 10 + buff[bp] - '0';
        next_char();
      }
      return *this;
    }
    InputReader& operator >> (double &num) {
      int intp = 0;
      while (isdigit(buff[bp]) == 0)
        next_char();
      while (isdigit(buff[bp])) {
        intp = intp * 10 + buff[bp] - '0';
        next_char();
      }
      num = 0.0;
      double p10 = 0.1;
      if (buff[bp] == '.')
        next_char();
      while (isdigit(buff[bp])) {
        num += p10 * (buff[bp] - '0');
        p10 /= 10;
        next_char();
      }
      num += intp;
      return *this;
    }
    void close() {
      fclose(fin);
    }
};

int main()
{
    int n;
    InputReader 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 = 150;
    for (int step = 0; step < (n <= 10000 ? 60 : 23); ++step) {
      int dir;
      double minD = 1e10;
      for (int d = 0; d < 8; ++d) {
        double dst = 0.0, a = xp + mv * dirx[d], b = yp + mv * diry[d];
        for (int i = 0; i < n; ++i)
          dst += sqrt((a - x[i]) * (a - x[i]) + (b - y[i]) * (b - y[i]));
        if (dst < minD) {
          minD = dst;
          dir = d;
        }
      }
      xp += mv * dirx[dir]; yp += mv * diry[dir];
      mv *= 0.6;
    }
    ofstream fout("adapost2.out");
    fout << setprecision(4) << fixed << xp << " " << yp;
    fout.close();
    return 0;
}