Pagini recente » Cod sursa (job #592948) | Cod sursa (job #1014344) | Cod sursa (job #620274) | Cod sursa (job #2485851) | Cod sursa (job #1929138)
#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;
}