Cod sursa(job #1081621)

Utilizator razvan9310FMI - Razvan Damachi razvan9310 Data 13 ianuarie 2014 19:34:37
Problema Adapost 2 Scor 82
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 2.77 kb
#include <fstream>
#include <vector>
#include <iomanip>
#include <cmath>
#include <iostream>
#define NMAX 50001
#define MAXDIST 1000000000
using namespace std;

class Punct {
    private:
        double x, y;

    public:
        Punct(const double &x_src = 0, const double &y_src = 0): x(x_src), y(y_src) {}

        double distanceTo(const Punct &p) const {
            return sqrt((x - p.x) * (x - p.x) + (y - p.y) * (y - p.y));
        }

        void setX(const double &x_src){
            x = x_src;
        }
        void setY(const double &y_src) {
            y = y_src;
        }

        double getX() const {
            return x;
        }

        double getY() const {
            return y;
        }
};

int N;
vector<Punct> puncte;
Punct best;

void input() {
    ifstream in("adapost2.in");
    in >> N;
    double xG = 0, yG = 0;

    for (int i = 0; i < N; ++i) {
        double x, y;
        in >> x >> y;
        xG += x, yG += y;

        Punct p(x, y);
        puncte.push_back(p);
    }

    xG /= N, yG /= N;

    best.setX(xG);
    best.setY(yG);

    in.close();
}

inline double squareDistanceToAll(const Punct &p) {
    double dist = 0;
    for (int i = 0; i < N; ++i) {
        dist += p.distanceTo(puncte[i]);
    }
    return dist;
}

Punct binSearch(double dist, Punct p, double current_dist) {

    /*for (int i = 0; i < 25; ++i) {//*/while (dist >= 0.001) {
        Punct up(p.getX(), p.getY() + dist);
        Punct down(p.getX(), p.getY() - dist);
        Punct left(p.getX() - dist, p.getY());
        Punct right(p.getX() + dist, p.getY());

        double up_dist = squareDistanceToAll(up);
        double down_dist = squareDistanceToAll(down);
        double left_dist = squareDistanceToAll(left);
        double right_dist = squareDistanceToAll(right);

        double min_dist = MAXDIST;
        if (up_dist < min_dist) {
            best = up;
            min_dist = up_dist;
        }

        if (down_dist < min_dist) {
            best = down;
            min_dist = down_dist;
        }

        if (left_dist < min_dist) {
            best = left;
            min_dist = left_dist;
        }

        if (right_dist < min_dist) {
            best = right;
            min_dist = right_dist;
        }

        if (min_dist < current_dist) {
            p = best;
            current_dist = min_dist;
        }

        dist /= 2.0;
    }

    return p;
}


void solve() {
    best = binSearch(2048 * 2, best, squareDistanceToAll(best));
}

inline void output() {
    ofstream out("adapost2.out");
    out << setprecision(10) << best.getX() << " " << best.getY();
    out.close();
}

int main() {
    input();
    solve();
    output();

    return 0;
}