Cod sursa(job #1696523)

Utilizator BrandonChris Luntraru Brandon Data 29 aprilie 2016 12:32:38
Problema Adapost 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.15 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-14;

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, step;

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.fi += pnt[i].fi;
    CurrPnt.se += pnt[i].se;
  }

  //CurrPnt = mp(1, 1);
  CurrPnt.fi /= n;
  CurrPnt.se /= n;

  CurrSum = Check(CurrPnt);
  step = 100;

  for(int iteration = 1; iteration <= 40; ++iteration) {
    Pe P1 = mp(CurrPnt.fi + dir[0][0] * step, CurrPnt.se + dir[0][1] * step);
    Pe P2 = mp(CurrPnt.fi + dir[1][0] * step, CurrPnt.se + dir[1][1] * step);
    Pe P3 = mp(CurrPnt.fi + dir[2][0] * step, CurrPnt.se + dir[2][1] * step);
    Pe P4 = mp(CurrPnt.fi + dir[3][0] * step, CurrPnt.se + dir[3][1] * step);

    double Dist1 = Check(P1);
    double Dist2 = Check(P2);
    double Dist3 = Check(P3);
    double Dist4 = Check(P4);

    Pe BestPnt = P1;
    double Ans = Dist1;

    if (Ans - Dist2 >= Eps) {
      BestPnt = P2;
      Ans = Dist2;
    }

    if (Ans - Dist3 >= Eps) {
      BestPnt = P3;
      Ans = Dist3;
    }

    if (Ans - Dist4 >= Eps) {
      BestPnt = P4;
      Ans = Dist4;
    }

    if (CurrSum - Ans >= Eps) {
      CurrPnt = BestPnt;
      CurrSum = Ans;
    }
    else {
      step /= 2;
    }

    /*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;
}