Cod sursa(job #2306717)

Utilizator lucametehauDart Monkey lucametehau Data 22 decembrie 2018 19:59:47
Problema Adapost 2 Scor 95
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <fstream>
#include <cmath>
#include <iomanip>

using namespace std;

ifstream cin ("adapost2.in");
ofstream cout ("adapost2.out");

typedef pair <double, double> pdd;

int n;
double s;
pdd sol;
bool ok;

pdd v[50005];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

double dist(pdd p) {
  double sol = 0;
  for(int i = 1; i <= n; i++)
    sol += sqrt((p.first - v[i].first) * (p.first - v[i].first) + (p.second - v[i].second) * (p.second - v[i].second));
  return sol;
}

int main() {
  cin >> n;
  for(int i = 1; i <= n; i++)
    cin >> v[i].first >> v[i].second;
  sol = {0, 0};
  s = dist(sol);
  for(double pas = 1000; pas >= 1e-4; pas /= 2) {
    ok = 1;
    for(int i = 0; i < 4; i++) {
      pdd p = {sol.first + dx[i] * pas, sol.second + dy[i] * pas};
      if(dist(p) < s) {
        sol = p;
        s = dist(p);
        ok = 0;
      }
    }
    if(!ok)
      pas *= 2;
  }
  cout << fixed << setprecision(4) << sol.first << " " << sol.second;
  return 0;
}