Cod sursa(job #956075)

Utilizator ericptsStavarache Petru Eric ericpts Data 2 iunie 2013 09:01:05
Problema Adapost 2 Scor 24
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <cstdio>
#include <utility>
#include <cmath>

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

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

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

inline float total_dist(const point &X)
{
    float 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;
    float step = 1000;
    bool changed;
    int i;
    while(step > EPS){
        changed = 0;
        float original = total_dist(P);
        float 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("%f %f\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("%f %f",&v[i].x,&v[i].y);
        SX += v[i].x;
        SY += v[i].y;
    }
    SX /= n;
    SY /= n;
    solve();
}