Cod sursa(job #2017174)

Utilizator mouse_wirelessMouse Wireless mouse_wireless Data 31 august 2017 13:54:58
Problema Adapost 2 Scor 82
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>
#include <climits>
#include <queue>
#include <ctime>
using namespace std;
typedef long long LL;

#ifdef INFOARENA
#define ProblemName "adapost2"
#endif

#define MCONCAT(A, B) A B
#ifdef ProblemName
#define InFile MCONCAT(ProblemName, ".in")
#define OuFile MCONCAT(ProblemName, ".out")
#else
#define InFile "fis.in"
#define OuFile "fis.out"
#endif

const int MAXN = 50000;
int N;
double x[MAXN], y[MAXN];
clock_t t0;

double dst(double ax, double ay, double bx, double by) {
  double dx = ax - bx, dy = ay - by;
  return sqrt(dx * dx + dy * dy);
}

double eval(double ex, double ey) {
  double ans = 0.0;
  for (int i = 0; i < N; ++i)
    ans += dst(ex, ey, x[i], y[i]);
  return ans;
}

double rand01() {
  return ((double)rand()) / RAND_MAX;
}

double getCurrentTime() {
  return (double)(clock() - t0) / CLOCKS_PER_SEC;
}

const double MAXC = 1100;
double bx, by, best;

void relax(double cx, double cy) {
  double cand = eval(cx, cy);
  if (cand < best) {
    best = cand;
    bx = cx, by = cy;
  }
}

int main() {
  t0 = clock();
  srand(12547);
  assert(freopen(InFile, "r", stdin));
  assert(freopen(OuFile, "w", stdout));
  scanf("%d", &N);
  for (int i = 0; i < N; ++i)
    scanf("%lf %lf", &x[i], &y[i]);
  bx = 500.0, by = 500.0; best = eval(bx, by);
  double t = 1.0; const double factor = 0.75;
  while (getCurrentTime() <= 0.18) {
    double dx = MAXC * rand01() * t, dy = MAXC * rand01() * t;
    relax(bx + dx, by + dy); relax(bx - dx, by + dy);
    relax(bx + dx, by - dy); relax(bx - dx, by - dy);
    relax(bx, by + dy); relax(bx, by - dy);
    relax(bx - dx, by); relax(bx + dx, by);
    t *= factor;
  }
  //fprintf(stderr, "%.8lf\n", t);
  printf("%.8lf %.8lf\n", bx, by);
  return 0;
}