Cod sursa(job #1758798)

Utilizator cristina_borzaCristina Borza cristina_borza Data 17 septembrie 2016 21:28:53
Problema Adapost 2 Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <fstream>
#include <cmath>

#define se second
#define fi first

using namespace std;

ifstream f ("adapost2.in");
ofstream g ("adapost2.out");

pair <double , double> point[50005];

int dx[] = {0 , 1 , 0 , -1,  0};
int dy[] = {0 , 0 , 1 , 0 , -1};
int n , dir;

double x = 1024 , y = 1024;

double dist (pair <double , double> a, pair <double , double> b);
double verif (double x, double y);

int main() {
    f >> n;

    for (int i = 1; i <= n; ++i) {
        f >> point[i].fi >> point[i].se;
    }

    double d = 1024;
    while (d > 0.0001) {
        double aux1 = verif (x , y);
        int ok = 0;

        for (int i = 1; i <= 4; ++i) {
            double aux2 = verif (x + dx[i] * d , y + dy[i] * d);
            if (aux2 < aux1) {
                x = x + dx[i] * d;
                y = y + dy[i] * d;
                ok = 1;
                break;
            }
        }

        if (!ok) {
            d /= 2;
        }
    }
    g << x << " " << y << '\n';
    return 0;
}

double dist (pair <double , double> a, pair <double , double> b) {
    double aux = (a.fi - b.fi) * (a.fi - b.fi) + (a.se - b.se) * (a.se - b.se);
    return (double)sqrt((double)(aux));
}

double verif (double x, double y) {
    pair <double , double> p2;
    double ans = 0;

    p2.fi = x;
    p2.se = y;

    for (int i = 1; i <= n; ++i) {
        ans += dist (point[i] , p2);
    }

    return ans;
}