Cod sursa(job #329427)

Utilizator DraStiKDragos Oprica DraStiK Data 6 iulie 2009 11:26:34
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda splunge1 Marime 1.35 kb
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#define MAX 1000
#define DIM 50005

struct punct {double x,y;} a[DIM],sol;
int dx[4]={1,0,-1, 0};
int dy[4]={0,1, 0,-1};
double min_tot;
int n;

void read ()
{
    int i;
    scanf ("%d",&n);
    for (i=1; i<=n; ++i)
        scanf ("%lf%lf",&a[i].x,&a[i].y);
}

double dist (double x,double y)
{
    double sum=0;
    int i;
    for (i=1; i<=n; ++i)
        sum+=sqrt ((x-a[i].x)*(x-a[i].x)+(y-a[i].y)*(y-a[i].y));
    return sum;
}

void solve ()
{
    double d[5],min,plm;
    int i,ind;
    punct t;
    for (t.x=rand ()%MAX+1, t.y=rand ()%MAX+1, min_tot=dist (t.x,t.y), plm=MAX; plm>0.001; )
    {
        for (i=0; i<4; ++i)
            d[i]=dist (t.x+dx[i]*plm,t.y+dy[i]*plm);
        min=d[0];
        ind=0;
        for (i=1; i<4; ++i)
            if (d[i]<min)
            {
                min=d[i];
                ind=i;
            }
        if (min<min_tot)
        {
            t.x+=dx[ind]*plm;
            t.y+=dy[ind]*plm;
            min_tot=min;
            sol=t;
        }
        else
            plm/=2;
    }
    printf ("%.4f %.4f",sol.x,sol.y);
}

int main ()
{
    freopen ("adapost2.in","r",stdin);
    freopen ("adapost2.out","w",stdout);
    srand (time (0));
    read ();
    solve ();
    return 0;
}