Cod sursa(job #1035792)

Utilizator DaNutZ2UuUUBB Bora Dan DaNutZ2UuU Data 18 noiembrie 2013 20:10:26
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <cmath>
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

struct Point {double x, y;};

ifstream fin("adapost2.in");
ofstream fout("adapost2.out");

const double EPSILON = 1e-3;

int N;
vector<Point> points;
Point result;
Point CG;

void hill_climbing();
inline double dist_sum(Point p);
inline double squared_dist(Point A, Point B);

int main() {
  fin >> N;
  points.resize(N);
  for (int i = 0; i < N; ++i) {
    fin >> points[i].x >> points[i].y;
    CG.x += points[i].x;
    CG.y += points[i].y;
  }
  CG.x /= N;
  CG.y /= N;

  hill_climbing();

  fout << result.x << ' ' << result.y;
}

void hill_climbing() {
  result = CG;

  double so_far = dist_sum(result);
  double cover = 256;
  bool improved = true;
  const int dx[] = {0, 1, 0, -1};
  const int dy[] = {1, 0, -1, 0};

  while (cover > EPSILON) {
    improved = false;
    for (int k = 0; k < 4; ++k) {
      Point p = {result.x + dx[k] * cover, result.y + dy[k] * cover};
      double tot_dist = dist_sum(p);
      if (tot_dist < so_far) {
        so_far = tot_dist;
        improved = true;
        result = p;
        break;
      }
    }
    if (!improved) {
      cover /= 2;
    }
  }
}

inline double dist_sum(Point p) {
  double result = 0;
  for (auto x : points) {
    result += squared_dist(p, x);
  }
  return result;
}

inline double squared_dist(Point A, Point B) {
  double result = 0;
  result += (A.x - B.x) * (A.x - B.x);
  result += (A.y - B.y) * (A.y - B.y);
  return sqrt(result);
}