Cod sursa(job #1929138)

Utilizator CodrutLemeniCodrut Lemeni CodrutLemeni Data 17 martie 2017 10:01:21
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <math.h>

using namespace std;

const int N = 50100 ;
const double MaxDistStep = 1000 ;
const double eps = 1e-4  ;
const double INFDOUBLE = 2000000000.0 ;

struct strpuncte{
    double x , y ;

};

int noPoints ;
strpuncte allPoints[ N ];

void CalcCenterOfGrav( strpuncte *pct ){
    static double xval , yval ;
    static int i ;

    xval = yval = 0 ;
    for ( i = 0 ; i < noPoints ; i++ ){
        xval += allPoints[ i ].x ;
        yval += allPoints[ i ].y ;
    }

    pct->x = xval / noPoints ;
    pct->y = yval / noPoints ;
}


double CalcDistance( strpuncte a , strpuncte b ){

    return sqrt( ( a.x - b.x ) * ( a.x - b.x ) + ( a.y - b.y ) * ( a.y - b.y ) );

}


double CalcSol( strpuncte pct ){
    static double sol ;
    static int i ;

    sol = 0 ;
    for ( i = 0; i < noPoints ; i++ ){
        sol += CalcDistance( pct , allPoints [ i ] );
    }

    return sol ;
}


int dx [] ={ 1 , - 1 , 0 , 0 };
int dy [] ={ 0 , 0 , 1 , - 1 };

int main(){
    int  i ;

    freopen("adapost2.in","r",stdin);
    freopen("adapost2.out","w",stdout);

    scanf("%d",&noPoints);

    for ( i = 0 ; i < noPoints ; i ++ ){
        scanf("%lf%lf" , &allPoints [ i ].x , &allPoints[ i ].y );
    }

    strpuncte bestPct ;

    CalcCenterOfGrav( &bestPct );

    double bestSol = CalcSol( bestPct );

    strpuncte crPct ;
    for ( double step = MaxDistStep ; step >= eps ; step /= 2 ){
        double crSol = INFDOUBLE ;

        for ( int k = 0 ; k < 4 ; k ++ ){
            strpuncte temp ;
            temp.x = bestPct.x + dx[ k ] * step ;
            temp.y = bestPct.y + dy[ k ] * step ;

            double tempval = CalcSol( temp );

            if ( tempval < crSol ){
                crPct = temp ;
                crSol = tempval ;
            }
        }

        if ( crSol < bestSol ){
            bestSol = crSol ;
            bestPct = crPct ;
            step *= 2;
        }

    }

    printf("%.4lf %.4lf ",bestPct.x , bestPct.y );

    return 0;
}