Cod sursa(job #63752)

Utilizator raula_sanChis Raoul raula_san Data 30 mai 2007 20:49:23
Problema Adapost 2 Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <cstdio>
#include <cmath>
#include <cstdlib>

#define dim 50001

int N;

double X[dim], Y[dim];

double d(double xa, double ya, double xb, double yb)
{
       return
             sqrt( (xa-xb)*(xa-xb) + (ya-yb)*(ya-yb) );
}

double suma(double x, double y)
{
       int i;
       
       double ret = 0;
       
       for(i=1; i<=N; ++i)
                ret += d(x, y, X[i], Y[i]);
                
       return ret;
}

int main()
{
    freopen("adapost2.in", "rt", stdin);
    freopen("adapost2.out", "wt", stdout);
    
    scanf("%d", &N);
    
    int i;
    
    double x, y, nx, ny, aprox, min, mi, s, xf, yf;
    
    for(i=1; i<=N; ++i)
			 scanf("%lf %lf", X+i, Y+i);
    
    x = rand() % 1000;
    y = rand() % 1000;
    
    min = suma(x, y);
    
    for(aprox=1; aprox>=0.0001; aprox/=10)
    {
                 do
                 {
                                mi = min;

								nx = x + aprox;
								ny = y;

								s = suma(nx, ny);

								if(s < min)
								{
									 min = s;
									 xf = nx;
									 yf = ny;
								}

								nx = x - aprox;
								ny = y;

								s = suma(nx, ny);

								if(s < min)
								{
									 min = s;
									 xf = nx;
									 yf = ny;
								}

								nx = x;
								ny = y + aprox;

								s = suma(nx, ny);

								if(s < min)
								{
									 min = s;
									 xf = nx;
									 yf = ny;
								}

								nx = x;
								ny = yf - aprox;

								s = suma(nx, ny);

								if(s < min)
								{
									 min = s;
									 xf = nx;
									 yf = ny;
								}

								if(min < mi)
									x = xf, y = yf;

				 } while(min < mi);

				 x = xf;
                 y = yf;
    }
    
    printf("%.4lf %.4lf", x, y);
    
    fclose(stdin);
    fclose(stdout);
    
    return 0;
}