Cod sursa(job #2067156)

Utilizator BogdanisarBurcea Bogdan Madalin Bogdanisar Data 15 noiembrie 2017 22:18:47
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.12 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;

// ideea de rezolvare se bazeaza pe presupunerea ca
// exista un singur punct de minim cerut, iar
// toate celelalte puncte converg doar catre acesta;

int N;
typedef pair<double,double> point;
point p[NMax];
// p[i] - al i-lea punct din input;

double getDist(point a,point b);
// getDist(a,b) return-eaza distanta euclidiana dintre cele doua puncte;
double getSum(point x);
// getSum(x) return-eaza suma distantelor de la fiecare punct din cele date la punctul x;
point solve();
// return-eaza un punct solutie;

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

    // se initializeaza punctul raspuns cu centrul de greutate;
    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;

    // se cauta cel mai bun punct prin mutari stanga,dreapta,sus,jos de lungime add;
    while (add > 1e-3) {

        // cat timp se poate ajunge inca la un punct mai bun folosind distanta add,
        // se face acest lucru;
        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;
            }

            // daca punctul la care ne aflam este mai optim decat cei 4 "vecini",
            // atunci trebuie micsorata distanta add de cautare;
            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);
}