Cod sursa(job #330434)

Utilizator warchildmdMihail Burduja warchildmd Data 9 iulie 2009 22:59:43
Problema Adapost 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#include<cstdio>
#include<math.h>

struct soldat
{
    float x;
    float y;
} sol[50001];

int N;

double distance(float x, float y)
{
    int i;
    double suma=0;
    for(i=1;i<=N;i++)
    {
        suma+=sqrt((sol[i].x-x)*(sol[i].x-x)+(sol[i].y-y)*(sol[i].y-y));
    }
    return suma;
}

int main()
{
    double eps=100.0000;
    freopen("adapost2.in","r",stdin);
    freopen("adapost2.out","w",stdout);
    scanf("%d",&N);
    int i;
    double sumax=0, sumay=0, locx, locy;
    for(i=1;i<=N;i++)
    {
        scanf("%lf %lf",&locx,&locy);
        sol[i].x=locx;
        sol[i].y=locy;
        sumax+=locx;
        sumay+=locy;
    }
    double currentx, currenty, bestx, besty, curr_dist, best_dist, last_dist;
    currentx=sumax/N;
    currenty=sumay/N;
    printf("%lf %fl\n",currentx,currenty);
    curr_dist=distance(currentx,currenty);
    while(eps>=0.0001)
    {
        best_dist=curr_dist;

        last_dist=distance(currentx+eps,currenty);
        if(last_dist<best_dist)
        {
            best_dist=last_dist;
            bestx=currentx+eps;
            besty=currenty;
        }

        last_dist=distance(currentx-eps,currenty);
        if(last_dist<best_dist)
        {
            best_dist=last_dist;
            bestx=currentx-eps;
            besty=currenty;
        }

        last_dist=distance(currentx,currenty+eps);
        if(last_dist<best_dist)
        {
            best_dist=last_dist;
            bestx=currentx;
            besty=currenty+eps;
        }

        last_dist=distance(currentx,currenty-eps);
        if(last_dist<best_dist)
        {
            best_dist=last_dist;
            bestx=currentx;
            besty=currenty-eps;
        }
        if(best_dist!=curr_dist)
        {
            curr_dist=best_dist;
            currentx=bestx;
            currenty=besty;
        }
        else
        {
            eps/=2.0;
        }
    }
    printf("%.4lf %.4lf",currentx,currenty);
    return 0;
}