Cod sursa(job #1759451)

Utilizator akaprosAna Kapros akapros Data 19 septembrie 2016 10:57:44
Problema Adapost 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <bits/stdc++.h>
#define maxN 50002
#define e 0.0000001
using namespace std;
int n;
double x, y, step;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
struct coord
{
    double x, y;
} v[maxN];
double Min(double x, double y)
{
    return x < y ? x : y;
}
void read()
{
    freopen("adapost2.in", "r", stdin);
    scanf("%d\n", &n);
    for (int i = 1; i <= n; ++ i)
        scanf("%lf %lf", &v[i].x, &v[i].y);
}
double dist(double x, double y)
{
    int i;
    double ans = 0.0;
    for (i = 1; i <= n; ++ i)
        ans += sqrt(1.0 * (x - v[i].x) * (x - v[i].x) + 1.0 * (y - v[i].y) * (y - v[i].y));
    return ans;
}
void get()
{
    double d = dist(x, y);
    while (step > e)
    {
        /// d = dist(x, y);
        double D = d;
        int i, p = -1;
        for (i = 0; i < 4; ++ i)
        {
            double di = dist(x + 1.0 * dx[i] * step, y + 1.0 * dy[i] * step);
            if (D - di >= e)
            {
                D = di;
                p = i;
            }
        }
        if (p == -1)
            step = 0.5 * step;
        else
        {
            x = x + 1.0 * dx[p] * step;
            y = y + 1.0 * dy[p] * step;
        }
        d = D;
    }
}
void solve()
{
    x = 0.0;
    y = 0.0;
    step = 500.0001;
    get();
}
void write()
{
    freopen("adapost2.out", "w", stdout);
    printf("%.4lf %.4lf", x, y);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}