Cod sursa(job #2278461)

Utilizator bleo16783FMI Bleotiu Cristian bleo16783 Data 8 noiembrie 2018 07:32:04
Problema Adapost 2 Scor 92
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.61 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 - X[it]) * (x - X[it]) + (y - Y[it]) * (y - Y[it]));
    return s;
}
void ts(double X[],double Y[],int n,double r,double &a,double &b,int dx[],int dy[])
{
    double curr_x,min_x,curr_y,min_y;
    double minim,D,prev_min;
    while(r > min_dif)
    {
        prev_min = minim;
        minim = inf;
        for(int d = 0; d < directions; ++d)
        {
            curr_x = a + dx[d] * r;
            curr_y = b + 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;
            }
        }
        if(minim < prev_min)
        {
            r = r * 2 / 3;
            a = min_x;
            b = min_y;
        }
        else
            r /= 2;
    }

    //if(r > min_dif)
      //  ts(X,Y,n,r * 2 / 3,min_x,min_y,dx,dy);

}
int main()
{
    ifstream fin("adapost2.in");
    ofstream fout("adapost2.out");
    int dx[4]= {1,0,-1,0};
    int dy[4]= {0,1,0,-1};
    double X[N],Y[N],x = 500, y = 500;
    int i,n;
    fin >> n;
    for(i = 0; i < n; ++i)
        fin >> X[i] >> Y[i];
    ts(X,Y,n,2000,x,y,dx,dy);
    fout << fixed << setprecision(4) << x << ' ' << setprecision(4) << y;
    return 0;
}