Cod sursa(job #956074)

Utilizator ericptsStavarache Petru Eric ericpts Data 2 iunie 2013 08:59:43
Problema Adapost 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <cstdio>
#include <utility>
#include <cmath>

using namespace std;
#define x first
#define y second
#define mp make_pair
typedef pair<double,double> point;

const int MAX_N = 50100;
const double EPS = 0.0001;
point v[MAX_N];
double SX,SY;
const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};
int n;

inline double dist(const point &A,const point &B)
{
    double delX,delY;
    delX = A.x - B.x;
    delY = A.y - B.y;
    delX *= delX;
    delY *= delY;
    return sqrt(delX+delY);
}

inline double total_dist(const point &X)
{
    double ret = 0;
    for(int i = 1 ; i <= n ; ++ i)
        ret += dist(X,v[i]);
    return ret;
}

void solve()
{
    point P = mp(SX,SY);
    point consider;
    double step = 1000;
    bool changed;
    int i;
    while(step > EPS){
        changed = 0;
        double original = total_dist(P);
        double posib;
        for(i = 0 ; i < 4 ; ++ i){
            consider = mp( P.x + step * dx[i],P.y + step * dy[i] );
            posib = total_dist(consider);
            if( posib < original){
                changed = 1;
                P = consider;
                break;
            }
        }
        if(!changed)
            step /= 2.0;
    }
    printf("%lf %lf\n",P.x,P.y);
}

int main()
{
    freopen("adapost2.in","r",stdin);
    freopen("adapost2.out","w",stdout);
    int i;
    scanf("%d",&n);
    for(i = 1 ; i <= n ; ++ i){
        scanf("%lf %lf",&v[i].x,&v[i].y);
        SX += v[i].x;
        SY += v[i].y;
    }
    SX /= n;
    SY /= n;
    solve();
}