Pagini recente » Cod sursa (job #1661281) | Cod sursa (job #2580755) | Cod sursa (job #1477439) | Monitorul de evaluare | Cod sursa (job #2937386)
#include <algorithm>
#include <fstream>
#include <cmath>
using namespace std;
ifstream cin( "adapost2.in" );
ofstream cout( "adapost2.out" );
const double INF = 2e8;
const double dl[] = { 0.0000, 0.0002, 0.0000, -0.0002 };
const double dc[] = { 0.0002, 0.0000, -0.0002, 0.0000 };
double patrat( double a ) {
return a * a;
}
struct points {
double x, y;
};
const int MAX = 5e4 + 1;
points v[ MAX ];
double X[ MAX ];
double Y[ MAX ];
points sol, P;
int n;
int main()
{
cin >> n;
for( int i = 0; i < n; i++ ) {
cin >> v[ i ].x >> v[ i ].y;
X[ i ] = v[ i ].x;
Y[ i ] = v[ i ].y;
}
sort( X, X + n );
sort( Y, Y + n );
double minn = INF;
sol = { X[ ( n + 1 ) / 2 ], Y[ ( n + 1 ) / 2 ] };
for( int pas = 512; pas > 0; pas >>= 1 )
for( int d = 0; d < 4; d++ ) {
double dis = 0;
P = { (double)pas * dl[ d ], (double)pas * dc[ d ] };
for( int i = 0; i < n; i++ )
dis += sqrt( patrat( sol.x + P.x - v[ i ].x ) + patrat( sol.y + P.y - v[ i ].y ) );
if( dis < minn ) {
minn = dis;
sol.x += P.x;
sol.y += P.y;
pas <<= 1;
d = 5;
}
}
cout << sol.x << ' ' << sol.y << '\n';
return 0;
}