Cod sursa(job #1083025)

Utilizator CosminRusuCosmin Rusu CosminRusu Data 15 ianuarie 2014 15:18:47
Problema Adapost 2 Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.02 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 int oo = 0x3f3f3f3f;

typedef vector<int> Graph[MAXN];
typedef vector<int> :: iterator It;

const inline int min(const int &a, const int &b) { if( a > b ) return b;   return a; }
const inline int max(const int &a, const int &b) { if( a < b ) return b;   return a; }
const inline void Get_min(int &a, const int b)    { if( a > b ) a = b; }
const inline void Get_max(int &a, const int b)    { if( a < b ) a = b; }

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

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

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) {
            pair<double, double> act;
            act.first = F.first + Move * dx[d];
            act.second = F.second + Move * dy[d];

            double now = Check(act);

            if(now < best) {
                best = now;
                F = act;
                Move *= 2;
                break;
            }
        }
    }

    fout << fixed << setprecision(4) << F.first << ' ' << F.second << '\n';
    fin.close();
    fout.close();
    return 0;
}