Cod sursa(job #2032067)

Utilizator RaduMirceaAndreiRadu Mircea Andrei RaduMirceaAndrei Data 4 octombrie 2017 14:53:59
Problema Adapost 2 Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
# include <fstream>
# include <cmath>
# include <iomanip>
# define DIM 50010
# define f first
# define s second
using namespace std;
ifstream fin("adapost2.in");
ofstream fout("adapost2.out");
pair<double,double> v[DIM];
int n,i;
double x,y,val,a,b,c,d,e;
inline double distanta(double a,double b,double c,double d){
    return sqrt((a-c)*(a-c)+(b-d)*(b-d));
}
inline double dist(double x,double y){
    double sum=0;
    for(int i=1;i<=n;i++)
        sum+=distanta(x,y,v[i].f,v[i].s);
    return sum;
}
int main () {
    fin>>n;
    for(i=1;i<=n;i++){
        fin>>v[i].f>>v[i].s;
        x+=v[i].f;
        y+=v[i].s;
    }
    x/=n;
    y/=n;
    for(double step=1024;step>0.0001;){
        a=dist(x+step,y);
        b=dist(x-step,y);
        c=dist(x,y+step);
        d=dist(x,y-step);
        e=dist(x,y);
        val=e;
        val=min(val,a);
        val=min(val,b);
        val=min(val,c);
        val=min(val,d);
        if(val==e){
            step/=2;
            continue;
        }
        if(val==a){
            x+=step;
            continue;
        }
        if(val==b){
            x-=step;
            continue;
        }
        if(val==c){
            y+=step;
            continue;
        }
        if(val==d){
            y-=step;
            continue;
        }
    }
    fout<<setprecision(4)<<fixed<<x<<" "<<y<<"\n";
    return 0;
}