Cod sursa(job #793460)

Utilizator repp4raduRadu-Andrei Szasz repp4radu Data 2 octombrie 2012 23:45:22
Problema Adapost 2 Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <fstream>
#include <cmath>
#include <iomanip>

#define EPS 1e-4
#define MAX 65536

using namespace std;

struct punct
{
    double x, y;
}v[MAX], G, now;

double dist, act;
int n, dX[] = {-1, 0, 1, 0}, dY[] = {0, 1, 0, -1};

inline double getDistance(punct a)
{
    double rez = 0.0;
    for(int i = 1; i <= n; i++)
    {
        double distX = a.x - v[i].x, distY = a.y - v[i].y;
        rez += (sqrt(distX * distX + distY * distY));
    }
    return rez;
}

int main()
{
    ifstream in("adapost2.in");
    in>>n;
    for(int i = 1; i <= n; i++)
    {
        in>>v[i].x>>v[i].y;
        G.x += v[i].x; G.y += v[i].y;
    } in.close();
    G.x /= n; G.y /= n; dist = getDistance(G);
    for(double adj = 512.0; adj > EPS; adj *= 0.5)
    {
        for(int i = 0; i < 4; i++)
        {
            now.x = G.x + dX[i] * adj; now.y = G.y + dY[i] * adj;
            act = getDistance(now);
            if(act < dist)
            {
                G.x = now.x; G.y = now.y;
                dist = act;
                adj *= 2;
                break;
            }
        }
    }
    ofstream out("adapost2.out");
    out<<fixed<<setprecision(4)<<G.x<<" "<<G.y;
    out.close();
    return 0;
}