Cod sursa(job #1758794)

Utilizator cristina_borzaCristina Borza cristina_borza Data 17 septembrie 2016 21:26:23
Problema Adapost 2 Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <fstream>
#include <cmath>

#define se second
#define fi first

using namespace std;

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

pair <long double , long double> point[1005];

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

long double x = 1024 , y = 1024;

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

int main() {
    f >> n;

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

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

        for (int i = 1; i <= 4; ++i) {
            long 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;
}

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

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

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

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

    return ans;
}