Pagini recente » Cod sursa (job #200485) | Cod sursa (job #987162) | Cod sursa (job #1482440) | Cod sursa (job #827058) | Cod sursa (job #793802)
Cod sursa(job #793802)
#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);
}
}
g << X_sol << " " << Y_sol;
}
int main(){
citeste();
rezolva();
f.close();
g.close();
return 0;
}