Cod sursa(job #1073086)

Utilizator razvan9310FMI - Razvan Damachi razvan9310 Data 5 ianuarie 2014 17:21:42
Problema Adapost 2 Scor 5
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 2.36 kb
#include <fstream>
#include <vector>
#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 squareDistanceTo(const Punct &p) const {
			return (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;
double maxX = 0, maxY = 0;
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;
		maxX = max(maxX, x);
		maxY = max(maxY, 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.squareDistanceTo(puncte[i]);
	}
	return dist;
}

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

	while (dist >= -0.001 && 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;
	}

	return p;
}

void solve() {
	Punct maxx(maxX, maxY);
	best = binSearch(best.squareDistanceTo(maxx), best, squareDistanceToAll(best));
}

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

int main() {
	input();
	solve();
	output();
	return 0;
}