Cod sursa(job #1711113)

Utilizator borcanirobertBorcani Robert borcanirobert Data 30 mai 2016 16:17:28
Problema Adapost 2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <fstream>
#include <iomanip>
#include <cmath>
using namespace std;

ifstream fin("adapost2.in");
ofstream fout("adapost2.out");

const int MAXN = 50010;
const float eps = 0.000001;
const int dx[] = { -1, 0, 1, 0 };
const int dy[] = { 0, 1, 0, -1 };
struct Point{
    float x, y;
};
int N;
Point a[MAXN];
float dist;
Point p;
float d1, d2, d3, d4;
Point p1, p2, p3, p4;
float coef;
float drez;
Point prez;

float Rez( Point x );

int main()
{
    int i, j;
    coef = 100;

    fin >> N;
    for ( i = 1; i <= N; i++ )
    {
        fin >> a[i].x >> a[i].y;
        p.x += a[i].x, p.y += a[i].y;
    }

    p.x /= N;
    p.y /= N;

    dist = drez = Rez(p);
    prez = p;

    for ( i = 1; i <= 35; i++ )
    {
        p1.x = p.x + dx[0]*coef, p1.y = p.y + dy[0]*coef;
        p2.x = p.x + dx[1]*coef, p2.y = p.y + dy[1]*coef;
        p3.x = p.x + dx[2]*coef, p3.y = p.y + dy[2]*coef;
        p4.x = p.x + dx[3]*coef, p4.y = p.y + dy[3]*coef;

        d1 = Rez(p1);
        d2 = Rez(p2);
        d3 = Rez(p3);
        d4 = Rez(p4);

        if ( dist - d1 >= eps )
        {
            dist = d1, p = p1;
        }
        if ( dist - d2 >= eps )
        {
            dist = d2, p = p2;
        }
        if ( dist - d3 >= eps )
        {
            dist = d3, p = p3;
        }
        if ( dist - d4 >= eps )
        {
            dist = d4, p = p4;
        }

        if ( drez - dist >= eps )
        {
            drez = dist;
            prez = p;
        }
        coef /= 2;
    }

    fout << fixed << setprecision(5) << prez.x << ' ' << prez.y << '\n';

    fin.close();
    fout.close();
    return 0;
}

float Rez( Point x )
{
    int i;
    float rez = 0.00000000;

    for ( i = 1; i <= N; i++ )
        rez = rez + sqrt( (x.x - a[i].x)*(x.x - a[i].x) + (x.y - a[i].y)*(x.y - a[i].y) );

    return rez;
}