Cod sursa(job #1759454)

Utilizator akaprosAna Kapros akapros Data 19 septembrie 2016 11:10:56
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.34 kb
#include <bits/stdc++.h>
#define maxN 50002
#define maxL 1000002
#define e 0.0000001
using namespace std;
int n, poz;
double x, y, step;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
char buff[maxL];
struct coord
{
    double x, y;
} v[maxN];
double Min(double x, double y)
{
    return x < y ? x : y;
}
void Read(double &numar)
{
    numar = 0;
    char semn='+';
    while (buff[poz] < '0' || buff[poz] > '9')
    {
        semn = buff[poz];
        if (++poz == maxL)
            fread(buff,1,maxL,stdin),poz=0;
    }
    while ('0'<=buff[poz] && buff[poz]<='9')
    {
        numar = numar*10 + buff[poz] - '0';
        if (++poz == maxL)
            fread(buff,1,maxL,stdin),poz=0;
    }
    if (buff[poz] == '.')
    {
        double tmp,cnt;
        tmp = 0;
        cnt = 1;
        ++poz;
        while ('0'<=buff[poz] && buff[poz]<='9')
        {
            cnt = cnt/10;
            tmp = tmp + cnt*(double(buff[poz]-'0'));
            if (++poz == maxL)
                fread(buff,1,maxL,stdin),poz=0;
        }
        numar += tmp;
    }
    if (semn == '-')
        numar = - numar;
}
void read()
{
    freopen("adapost2.in", "r", stdin);
    scanf("%d\n", &n);
    for (int i = 1; i <= n; ++ i)
    {
        Read(v[i].x);
        Read(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 = 4;
        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 == 4)
            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;
}