Cod sursa(job #1081636)

Utilizator razvan9310FMI - Razvan Damachi razvan9310 Data 13 ianuarie 2014 19:50:54
Problema Adapost 2 Scor 90
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 2.47 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) {
	if (dist <= 0.0001) {
		return p;
	}

	Punct right(p.getX() + dist, p.getY());
	double right_dist = squareDistanceToAll(right);
	if (current_dist - right_dist > 0.0001) {
		return binSearch(dist, right, right_dist);
	}

	Punct left(p.getX() - dist, p.getY());
	double left_dist = squareDistanceToAll(left);
	if (current_dist - left_dist > 0.0001) {
		return binSearch(dist, left, left_dist);
	}

	Punct down(p.getX(), p.getY() - dist);
	double down_dist = squareDistanceToAll(down);
	if (current_dist - down_dist > 0.0001) {
		return binSearch(dist, down, down_dist);
	}

	Punct up(p.getX(), p.getY() + dist);
	double up_dist = squareDistanceToAll(up);
	if (current_dist - up_dist > 0.0001) {
		return binSearch(dist, up, up_dist);
	}

	return binSearch(dist / 2.0, p, current_dist);
}


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;
}