Cod sursa(job #2278448)

Utilizator bleo16783FMI Bleotiu Cristian bleo16783 Data 8 noiembrie 2018 05:23:36
Problema Adapost 2 Scor 85
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>
using namespace std;
#define N 50500
#define min_dif 0.000001
#define inf 100500000
#define directions 4
struct punct
{
    double x,y;
    punct()
    {
        x = 0;
        y = 0;
    }
};
double dist(punct a,punct b)
{
    return sqrt((a.x-b.x) * (a.x-b.x) + (a.y-b.y) * (a.y-b.y));
}
double total_dist(punct a,punct v[],int dim) ///distanta totala
{
    double s = 0;
    for(int it = 0; it < dim; ++it)
        s += dist(a,v[it]);
    return s;
}
/*double total_dist1(punct a,punct v[],int dim) ///distanta maxima
{
    double max_distanta = 0;
    for(int it = 0; it < dim; ++it)
        max_distanta = max(max_distanta,dist(a,v[it]));
    return max_distanta;
}*/
punct ts(punct v[],int n,double r,punct center,double dx[],double dy[])
{
    punct curr,pmin;
    double minim = inf,D;
    for(int d = 0;d < directions; ++d)
    {
        curr.x = center.x + dx[d] * r;
        curr.y = center.y + dy[d] * r;
        D = total_dist(curr,v,n);
        if(D < minim)
        {
            pmin = curr;
            minim = D;
        }
    }
    if(r < min_dif)
        return pmin;
    return ts(v,n,r * 2 / 3,pmin,dx,dy);
}
int main()
{
    ifstream fin("adapost2.in");
    ofstream fout("adapost2.out");
    punct v[N],ans,centru;
    centru.x = 500;
    centru.y = 500;
    double dx[4]={1,0,-1,0};
    double dy[4]={0,1,0,-1};
    int i,n;
    fin >> n;
    for(i = 0; i < n; ++i)
        fin >> v[i].x >> v[i].y;
    ans = ts(v,n,2000,centru,dx,dy);
    centru.x = 4.1442;centru.y=4.2898;
    fout <</* total_dist(ans,v,n)<<' ' <<*/ fixed << setprecision(4) << ans.x << ' ' << setprecision(4) << ans.y;
    return 0;
}