Cod sursa(job #2045530)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 22 octombrie 2017 14:54:12
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include<fstream>
#include<iomanip>
#include<cmath>
#include<cstdio>
#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};
FILE * fin = fopen("adapost2.in", "r");
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(){
    fscanf(fin, "%d", &n);
    for(i = 1; i <= n; i++){
        fscanf(fin, "%lf%lf", &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;
}