Cod sursa(job #2075461)

Utilizator MaligMamaliga cu smantana Malig Data 25 noiembrie 2017 14:19:49
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.64 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <iomanip>

#if 1
#define pv(x) cout<<#x<<" = "<<x<<"; ";cout.flush()
#define pn cout<<endl
#else
#define pv(x)
#define pn
#endif

using namespace std;
ifstream in("adapost2.in");
ofstream out("adapost2.out");

#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
const int NMax = 5e4 + 5;
const int mod = 666013;

int N;
typedef pair<double,double> point;
point v[NMax];

point solve();
double getSum(point);

int main() {
    in>>N;
    for (int i=1;i <= N;++i) {
        in>>v[i].first>>v[i].second;
    }

    point adapost = solve();
    out<<fixed<<setprecision(6)<<adapost.first<<' '<<adapost.second<<'\n';

    return 0;
}

point solve() {

    point adapost = mp(0,0);
    for (int i=1;i <= N;++i) {
        adapost.first += v[i].first;
        adapost.second += v[i].second;
    }
    adapost.first /= N;
    adapost.second /= N;

    double add = 100;
    while (add > 1e-3) {

        while (true) {
            point top = mp(adapost.first,adapost.second + add),
                  bot = mp(adapost.first,adapost.second - add),
                  st = mp(adapost.first - add,adapost.second),
                  dr = mp(adapost.first + add,adapost.second);

            double sumTop = getSum(top),
                   sumBot = getSum(bot),
                   sumSt = getSum(st),
                   sumDr = getSum(dr),
                   sumAdapost = getSum(adapost);

            bool update = false;
            if (sumTop < sumAdapost) {
                sumAdapost = sumTop;
                adapost = top;
                update = true;
            }
            if (sumBot < sumAdapost) {
                sumAdapost = sumBot;
                adapost = bot;
                update = true;
            }
            if (sumSt < sumAdapost) {
                sumAdapost = sumSt;
                adapost = st;
                update = true;
            }
            if (sumDr < sumAdapost) {
                sumAdapost = sumDr;
                adapost = dr;
                update = true;
            }

            if (!update) {
                break;
            }
        }

        add /= 2;
    }

    return adapost;
}

double getDist(point a,point b) {
    double val = (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
    return sqrt(val);
}

double getSum(point x) {
    double ans = 0;

    for (int i=1;i <= N;++i) {
        ans += getDist(v[i],x);
    }

    return ans;
}