Cod sursa(job #956078)

Utilizator ericptsStavarache Petru Eric ericpts Data 2 iunie 2013 09:12:28
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 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.0005;
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;
    float step = 512;
    bool changed;
    double best_so_far = total_dist(P);
    double posib;
    int i;
    while(step > EPS){
        changed = 0;
        for(i = 0 ; i < 4 ; ++ i){
            consider = mp( P.x + step * dx[i],P.y + step * dy[i] );
            posib = total_dist(consider);
            if( posib < best_so_far){
                changed = 1;
                P = consider;
                best_so_far = posib;
                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();
}