Cod sursa(job #63757)

Utilizator raula_sanChis Raoul raula_san Data 30 mai 2007 20:55:51
Problema Adapost 2 Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.2 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, maxx, minx, maxy, miny;
    
    maxx = maxy = -1;
    minx = miny = 1001;
    
    for(i=1; i<=N; ++i)
    {
			 scanf("%lf %lf", X+i, Y+i);
       
             if(X[i] < minx) minx = X[i];
             if(X[i] > maxx) maxx = X[i];
             
             if(Y[i] < miny) miny = Y[i];
             if(Y[i] > maxy) maxy = Y[i];
    }
    
//    x = rand() % 1000;
//    y = rand() % 1000;
  
    x = (maxx + minx) / 2;
    y = (maxy + miny) / 2;
    
    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;
}