Cod sursa(job #1048754)

Utilizator razvan9310FMI - Razvan Damachi razvan9310 Data 6 decembrie 2013 12:55:02
Problema Adapost 2 Scor 72
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.42 kb
#include <fstream>
#include <vector>
#include <iomanip>
#include <cmath>
#include <iostream>
#define NMAX 50001
#define MAXDIST 1000000000
using namespace std;

class Punct {
	private:
		long double x, y;

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

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

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

		long double getX() const {
			return x;
		}

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

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

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

	for (int i = 0; i < N; ++i) {
		long 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 long double squareDistanceToAll(const Punct &p) {
	long double dist = 0;
	for (int i = 0; i < N; ++i) {
		dist += p.distanceTo(puncte[i]);
	}
	return dist;
}

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

	for (int i = 0; i < 35; ++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());

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

		long 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(1024, 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;
}