Cod sursa(job #2518725)

Utilizator rapunzelMihnea Andreescu rapunzel Data 6 ianuarie 2020 14:56:55
Problema Adapost 2 Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <fstream>
#include <iomanip>
#include <cmath>

using namespace std;

ifstream cin("adapost2.in");
ofstream cout("adapost2.out");

const int N = 50000 + 7;
const int P = 50;
int n;
double x[N];
double y[N];

double dist(double a, double b, int i)
{
    double dx = a - x[i];
    double dy = b - y[i];
    return sqrt(dx * dx + dy * dy);
}

double dist(double a, double b)
{
    double ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ans += dist(a, b, i);
    }
    return ans;
}

double dist(double a)
{
    double l = 0, r = 1000;
    for (int i = 1; i <= 50; i++)
    {
        double m = (l + r) * 0.5;
        if (dist(a, m) >= dist(a, m + 0.0001))
        {
            l = m;
        }
        else
        {
            r = m;
        }
    }
    return dist(a, l);
}

double get(double a)
{
    double l = 0, r = 1000;
    for (int i = 1; i <= P; i++)
    {
        double m = (l + r) * 0.5;
        if (dist(a, m) >= dist(a, m + 0.0001))
        {
            l = m;
        }
        else
        {
            r = m;
        }
    }
    return l;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> x[i] >> y[i];
    }
    double l = 0, r = 1000;
    for (int i = 1; i <= P; i++)
    {
        double m = (l + r) * 0.5;
        if (dist(m) >= dist(m + 0.0001))
        {
            l = m;
        }
        else
        {
            r = m;
        }
    }
    cout << fixed << setprecision(6) << l << " " << get(l) << "\n";
}