Cod sursa(job #2937386)

Utilizator andrei_marciucMarciuc Andrei andrei_marciuc Data 10 noiembrie 2022 11:38:15
Problema Adapost 2 Scor 95
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#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;
}