Cod sursa(job #2067151)

Utilizator MaligMamaliga cu smantana Malig Data 15 noiembrie 2017 22:10:58
Problema Adapost 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.32 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>

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

#define ll long long
#define ull unsigned long long
#define pb push_back
const int NMax = 5e4 + 5;
const int sqMax = 320 + 5;

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

double getDist(point a,point b);
double getSum(point x);
point solve();

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

    point adapost = solve();
    out<<fixed<<setprecision(4)<<adapost.first<<' '<<adapost.second;

    in.close();out.close();
    return 0;
}

point solve() {
    point adapost = point(0,0);

    for (int i=1;i <= N;++i) {
        adapost.first += p[i].first;
        adapost.second += p[i].second;
    }
    adapost.first /= N;
    adapost.second /= N;

    double add = 100;

    while (add > 1e-4) {

        while (true) {
            point pTop = point(adapost.first,adapost.second + add);
            point pBot = point(adapost.first,adapost.second - add);
            point pLeft = point(adapost.first - add,adapost.second);
            point pRight = point(adapost.first + add,adapost.second);

            double sumTop = getSum(pTop), sumBot = getSum(pBot),
                   sumLeft = getSum(pLeft), sumRight = getSum(pRight);

            double mn = min(min(sumTop,sumBot),min(sumLeft,sumRight));
            point minPoint;

            if (mn == sumTop) {
                minPoint = pTop;
            }
            else if (mn == sumBot) {
                minPoint = pBot;
            }
            else if (mn == sumLeft) {
                minPoint = pLeft;
            }
            else {
                minPoint = pRight;
            }

            if (mn >= getSum(adapost)) {
                break;
            }
            else {
                adapost = minPoint;
            }
        }

        add /= 2;
    }

    return adapost;
}

double getSum(point a) {
    double ret = 0;
    for (int i=1;i <= N;++i) {
        ret += getDist(a,p[i]);
    }

    return ret;
}

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);
}