Cod sursa(job #2278457)

Utilizator bleo16783FMI Bleotiu Cristian bleo16783 Data 8 noiembrie 2018 07:05:34
Problema Adapost 2 Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>
using namespace std;
#define N 50500
#define min_dif 0.00001
#define inf 100500000
#define directions 4
double total_dist(double x,double y,double X[],double Y[],int dim) ///distanta totala
{
    double s = 0;
    for(int it = 0; it < dim; ++it)
        s += sqrt((X[it]-x) * (X[it]-x) + (Y[it]-y) * (Y[it]-y));
    return s;
}
pair<double,double> ts(double X[],double Y[],int n,double r,double x,double y,int dx[],int dy[])
{
    double curr_x,curr_y,min_x,min_y;
    double minim,D,curr_D;
    int d;
    minim = total_dist(x,y,X,Y,n);
    while(r > min_dif)
    {
        curr_D = minim;
        for(d = 0;d < directions; ++d)
        {
            curr_x = x + dx[d] * r;
            curr_y = y + dy[d] * r;
            D = total_dist(curr_x,curr_y,X,Y,n);
            if(D < minim)
            {
                min_x = curr_x;
                min_y = curr_y;
                minim = D;
            }
        }
        r *= 0.66;
        x = min_x;
        y = min_y;
    }
    pair<double,double> answer;
    answer.first = x;
    answer.second = y;
    return answer;
}
int main()
{
    ifstream fin("adapost2.in");
    ofstream fout("adapost2.out");
    double X[N],Y[N],r = 1000,x = 500,y = 500,curr_x,curr_y,min_x,min_y,D,minim;
    int d;
    int dx[4]={1,0,-1,0};
    int dy[4]={0,1,0,-1};
    int i,n;
    fin >> n;
    for(i = 0; i < n; ++i)
        fin >> X[i] >> Y[i];
    pair<double,double> ans = ts(X,Y,n,2000,500,500,dx,dy);
    fout << setprecision(4) << fixed << ans.first << ' ' << ans.second;
    return 0;
}