Cod sursa(job #1083030)

Utilizator CosminRusuCosmin Rusu CosminRusu Data 15 ianuarie 2014 15:22:22
Problema Adapost 2 Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <fstream>
#include <vector>
#include <bitset>
#include <math.h>
#include <iomanip>

using namespace std;

const char infile[] = "adapost2.in";
const char outfile[] = "adapost2.out";

ifstream fin(infile);
ofstream fout(outfile);

const int MAXN = 50005;
const double EPS = 1e-4;

const double dx[] = {1, 0, -1, 0};
const double dy[] = {0,-1,  0, 1};

int N;
pair<double, double> P[MAXN], F, act;
double best, now;

inline double sqr(const double a) {
    return a * a;
}

inline double dist(pair<double, double> a, pair<double, double> b) {
    return sqrt(sqr(a.first - b.first) + sqr(a.second - b.second));
}

inline double Check(const pair<double, double> R) {
    double ret = 0;
    for(int i = 1 ; i <= N ; ++ i)
        ret += dist(P[i], R);
    return ret;
}

int main() {
    fin >> N;
    for(int i = 1 ; i <= N ; ++ i) {
        fin >> P[i].first >> P[i].second;
        F.first += P[i].first;
        F.second += P[i].second;
    }
    F.first /= 1.0 * N;
    F.second /= 1.0 * N;
    best = Check(F);

    for(double Move = 16 ; Move > EPS ; Move /= 2.0) {
        for(int d = 0 ; d < 4 ; ++ d) {
            act.first = F.first + Move * dx[d];
            act.second = F.second + Move * dy[d];
            now = Check(act);
            if(now < best) {
                best = now;
                F = act;
                Move *= 2.0;
                break;
            }
        }
    }
    fout << fixed << setprecision(4) << F.first << ' ' << F.second << '\n';
    fin.close();
    fout.close();
    return 0;
}