Cod sursa(job #1758796)

Utilizator cristina_borzaCristina Borza cristina_borza Data 17 septembrie 2016 21:27:45
Problema Adapost 2 Scor 75
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 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[50005];
int n;

long double dist (pair <long double , long double> a, pair <long double , long double> b);
long double verif (long double x, long double y);
pair <long double , long double> solve (long double x , long double y , long double d , int dir);

int main() {
    f >> n;

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

    pair <long double , long double> ans = solve (1024 , 1024 , 1024 , 0);
    g << ans.fi << " " << ans.se << '\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;
}

pair <long double , long double> solve (long double x , long double y , long double d , int dir) {
    if (d < 0.0001) {
        return make_pair(x , y);
    }

    long double aux = verif (x , y);
    if (dir != 3 && verif (x - d , y - d) < aux) {
        return (solve (x - d , y - d , d , 1));
    }

    if (dir != 4 && verif (x - d , y + d) < aux) {
        return (solve (x - d , y + d , d , 2));
    }

    if (dir != 2 && verif (x + d , y - d) < aux) {
        return (solve (x + d , y - d , d , 4));
    }

    if (dir != 1 && verif (x + d , y + d) < aux) {
        return (solve (x + d , y + d , d , 3));
    }

    return solve (x , y , d / 2 , dir);
}