Cod sursa(job #2083125)

Utilizator karenalo13Diaconu Iulian Andrei karenalo13 Data 7 decembrie 2017 03:55:02
Problema Adapost 2 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.58 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>

using namespace std;
ifstream f("adapost2.in");
ofstream g("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> punct;
punct p[50005];


double distanta(punct a,punct b)
{
    return  sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));

}
double suma(punct a)
{
    double ret = 0;
    for (int i=1; i <= N; ++i)
    {
        ret += distanta(a,p[i]);
    }

    return ret;
}

punct solve()
{
    int i; punct adapost;
    adapost.first = p[1].first;
    adapost.second = p[1].second;

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

    double add = 100;
    while (add > 0.0001)
    {

        // pana ajungem la un punct apropiat , tot micim distanta cu add
        // CAUTAM punctul sus , jos , stanga , dreapta , si comparam cu cel din mijloc
        //alegem punctul cel mai "bun"
          punct sus,jos,stanga,dreapta;
            sus.first = adapost.first;sus.second=adapost.second + add;
            jos.first = adapost.first;jos.second=adapost.second - add;
            stanga.first = adapost.first - add;stanga.first=adapost.first;
            dreapta.first = adapost.first + add;dreapta.first =adapost.first;
            double sumsus = suma(sus), sumjos= suma(jos), sumstanga = suma(stanga), sumdreapta = suma(dreapta);

            double mn = min(min(sumsus,sumjos),min(sumstanga,sumdreapta));
            punct minpunct;

            if (mn == sumsus)
            {
                minpunct = sus;
            }
            else if (mn == sumjos)
            {
                minpunct = jos;
            }
            else if (mn == sumstanga)
            {
                minpunct = stanga;
            }
            else
            {
                minpunct = dreapta;
            }
            if (mn >= suma(adapost))
            {
                break;
            }
            else
            {
                adapost = minpunct;
            }


        add /= 2;
    }

    return adapost;
}




int main()
{
    f>>N;
    for (int i=1; i <= N; ++i)
    {
        f>>p[i].first>>p[i].second;
    }
punct adapost;
     adapost = solve();
    g<<fixed<<setprecision(4)<<adapost.first<<' '<<adapost.second;


    return 0;
}