Cod sursa(job #1234934)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 28 septembrie 2014 13:03:59
Problema Adapost 2 Scor 86
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <fstream>
#include <iomanip>
#include <cmath>

#define NMAX 50005
using namespace std;

int n;
struct punct
{
    double x,y;
    punct(double x=0,double y=0): x(x), y(y) {}
}v[NMAX];

double dist(const punct &a,const punct &b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

double dist_tot(const punct &a){
    double total=0;
    for(int i=1;i<=n;i++)
        total+=dist(a,v[i]);

    return total;
}

int main()
{
    ifstream cin("adapost2.in");
    ofstream cout("adapost2.out");

    cin>>n;

    double x=0,y=0,aux;
    for(int i=1;i<=n;i++){
        cin>>v[i].x>>v[i].y;
        x+=v[i].x;y+=v[i].y;
    }

    x/=n;y/=n;

    double minim=dist_tot(punct(0,0));
    double step=1000;

    for(int i=1;i<=30;i++){
        //while(1){
            aux=dist_tot(punct(x+step,y));
            if(aux<minim){
                minim=aux;
                x+=step;
                continue;
            }

            aux=dist_tot(punct(x-step,y));
            if(aux<minim){
                minim=aux;
                x-=step;
                continue;
            }

            aux=dist_tot(punct(x,y+step));
            if(aux<minim){
                minim=aux;
                y+=step;
                continue;
            }

            aux=dist_tot(punct(x,y-step));
            if(aux<minim){
                minim=aux;
                y-=step;
                continue;
            }

            //break;
        //}

        step/=2.0;
    }

    cout<<fixed<<setprecision(4)<<x<<' '<<y<<'\n';

    cin.close();
    cout.close();
    return 0;
}