Cod sursa(job #1696502)

Utilizator BrandonChris Luntraru Brandon Data 29 aprilie 2016 11:56:42
Problema Adapost 2 Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.18 kb
#include <fstream>
#include <cmath>
#include <iomanip>

#define Pe pair <double, double>
#define mp make_pair
#define fi first
#define se second
using namespace std;

const int MaxN = 50005;
const double Eps = 1e-4;

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

Pe pnt[MaxN], CurrPnt;

double dir[4][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
int n;
double CurrSum, BestSum;

inline double Dist(const Pe &a, const Pe &b) {
  return sqrt((a.fi - b.fi) * (a.fi - b.fi) + (a.se - b.se) * (a.se - b.se));
}

inline double Check(const Pe &CandPnt) {
  double ans = 0;

  for (int i = 1; i <= n; ++i) {
    ans += Dist(pnt[i], CandPnt);
  }

  return ans;
}

inline bool InBound(Pe CandPnt, const int &direction, const double &step) {
  CandPnt.fi += dir[direction][0] * step;
  CandPnt.se += dir[direction][1] * step;

  bool InBoundFi = (CandPnt.fi <= 1000 and CandPnt.fi >= 1);
  bool InBoundSe = (CandPnt.se <= 1000 and CandPnt.se >= 1);

  return InBoundFi and InBoundSe;
}

int main() {
  cin >> n;

  for (int i = 1; i <= n; ++i) {
    cin >> pnt[i].fi >> pnt[i].se;
  }

  CurrPnt = mp(1, 1);
  CurrSum = Check(CurrPnt);

  for(int iteration = 1; iteration <= 40; ++iteration) {
    Pe BestPnt = CurrPnt;
    int BestDir = -1;
    BestSum = Check(CurrPnt);
    CurrSum = BestSum;

    for (int i = 0; i < 4; ++i) {
      Pe NewPnt;
      NewPnt.fi = CurrPnt.fi + dir[i][0] * Eps;
      NewPnt.se = CurrPnt.se + dir[i][1] * Eps;

      double NewSum = Check(NewPnt);

      if (NewSum < BestSum) {
        BestDir = i;
        BestSum = NewSum;
      }
    }

    double step = 100;
    BestPnt.fi = CurrPnt.fi + dir[BestDir][0] * step;
    BestPnt.se = CurrPnt.se + dir[BestDir][1] * step;
    BestSum = Check(BestPnt);

    while ((!InBound(CurrPnt, BestDir, step) or step > Eps) and CurrSum < BestSum) {
      step /= 2;
      BestPnt.fi = CurrPnt.fi + dir[BestDir][0] * step;
      BestPnt.se = CurrPnt.se + dir[BestDir][1] * step;
      BestSum = Check(BestPnt);
    }

    CurrPnt = BestPnt;
  }
  //}while (BestSum < CurrSum);

  cout << fixed << setprecision(4) << CurrPnt.fi << ' ' << CurrPnt.se << '\n';
  return 0;
}