Cod sursa(job #793801)

Utilizator vendettaSalajan Razvan vendetta Data 4 octombrie 2012 10:38:24
Problema Adapost 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <cmath>

using namespace std;

ifstream f("adapost2.in");
ofstream g("adapost2.out");

#define nmax 50005

const double new_x[] = {1, 0.1, 0.01, 0.001, 0.0001};
int n;
pair<double, double> v[nmax];
queue<pair<double, double> > q;
double Min, X_sol, Y_sol;

void citeste(){

	f >> n;
	for(int i=1; i<=n; ++i){
		double x, y;
		f >> x >> y;
		v[i] = make_pair(x,y);
	}

}

void incearca(double X, double Y){

	double new_min = 0.0;
	for(int i=1; i<=n; ++i){
		double A = (v[i].first - X) * (v[i].first - X);
		double B = (v[i].second - Y) * (v[i].second - Y);
		double Dist = sqrt(A+B);
		new_min += Dist;
	}

	if (new_min < Min){
		q.push(make_pair(X,Y));
		X_sol = X;
		Y_sol = Y;
		Min = new_min;
	}

}

void rezolva(){

	//ideea ar fi ca : pornesc din (0,0) si tot mut acestpunct la dreapta/stanga/sus/jos
	//cat timp obtin o solutie ma ibuna

	q.push(make_pair(0.0, 0.0));
	Min = 265477893.0;
	incearca(0.0, 0.0);

	for(; q.size(); ){
		double X = q.front().first;
		double Y = q.front().second;
		q.pop();
		for(int k=0; k<5; ++k){
			//ma duc in sus
			double xx = X + new_x[k];
			double yy = Y;
			incearca(xx,yy);
			//ma duc in jos
			xx = X - new_x[k];
			yy = Y;
			incearca(xx,yy);
			//ma duc in stanga;
			xx = X;
			yy = Y - new_x[k];
			incearca(xx,yy);
			//ma duc in dreapta;
			xx = X;
			yy = Y + new_x[k];
			incearca(xx,yy);
		}
	}

	cout << X_sol << " " << Y_sol;

}

int main(){

    citeste();
    rezolva();

    f.close();
    g.close();

    return 0;

}