Cod sursa(job #1071029)

Utilizator dariusdariusMarian Darius dariusdarius Data 2 ianuarie 2014 14:45:48
Problema Adapost 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>

#include<algorithm>
#include<fstream>
#include<iomanip>

#define x first
#define y second
using namespace std;
const int MAX_N = 50000 + 5;
const double MAX_PAS = 16.0;
const double EPS_PAS = 0.0001;
const double EPS = 0.0000000001;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
int n;
pair<double,double> points[MAX_N];

double distance(const pair<double,double> &a, const pair<double,double> &b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
double cost(const pair<double,double> &point) {
    double answer=0.0;
    for(int i = 1; i <= n; ++i) {
        answer += distance(point, points[i]);
    }
    return answer;
}

int main() {
    ifstream fin("adapost2.in");
    ofstream fout("adapost2.out");
    pair<double,double> answer(0,0),next_answer;
    fin >> n;
    for(int i = 1; i <= n; ++i) {
        fin >> points[i].x >> points[i].y;
        answer.x += points[i].x;
        answer.y += points[i].y;
    }
    answer.x /= n;
    answer.y /= n;

    double best_cost = cost(answer), current_cost;
    for(double pas = MAX_PAS; pas >= EPS_PAS; pas *= 0.5) {
        bool increase_pas=false;
        for(int d = 0; d < 4; ++d) {
            next_answer.x = answer.x + pas * dx[d];
            next_answer.y = answer.y + pas * dy[d];
            current_cost = cost(next_answer);
            if(best_cost - current_cost >= EPS) {
                best_cost = current_cost;
                answer = next_answer;
                increase_pas = true;
                break;
            }
        }
        if(increase_pas) {
            pas *= 2.0;
        }
    }

    fout << setprecision(4) << fixed;
    fout << answer.x << " " << answer.y << endl;
    return 0;
}