Cod sursa(job #2045441)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 22 octombrie 2017 13:27:09
Problema Adapost 2 Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include<fstream>
#include<iomanip>
#include<cmath>
#define x first
#define y second
using namespace std;
int n, i, ok;
double aria, sol, ii;
pair<double, double> v[50005], p, p2, aux;
int di[5] = {0, -1, 1, 0, 0};
int dj[5] = {0, 0, 0, -1, 1};
ifstream fin("adapost2.in");
ofstream fout("adapost2.out");
double calc(pair<double, double> p){
    double aria = 0;
    for(int i = 1; i <= n; i++){
        aria += sqrt( (p.x - v[i].x) * (p.x - v[i].x) + (p.y - v[i].y) * (p.y - v[i].y) );
    }
    return aria;
}
int main(){
    fin>> n;
    for(i = 1; i <= n; i++){
        fin>> v[i].x >> v[i].y;
        p.x += v[i].x;
        p.y += v[i].y;
    }
    p.x /= n;
    p.y /= n;
    sol = calc(p);
    ii = 1000;
    while(ii > 0.0001){
        ok = 0;
        for(i = 1; i <= 4; i++){
            p2.x = p.x + ii * di[i];
            p2.y = p.y + ii * dj[i];
            aria = calc(p2);
            if(sol > aria){
                sol = aria;
                ok = 1;
                p = p2;
            }
        }
        if(ok == 0){
            ii /= 2.0;
        }
    }
    fout<< setprecision(4) << fixed << p.x <<" "<< setprecision(4) << fixed << p.y <<"\n";
    return 0;
}