Cod sursa(job #1077945)

Utilizator costel93FMI - Dumea Eduard Constantin costel93 Data 11 ianuarie 2014 20:45:50
Problema Adapost 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <fstream>
#include <iostream>
#include <math.h>

using namespace std;

int n, m, i, j ;

double x[50005], y[50005], sol, x_sol, y_sol, sol_aux, xx, yy;

int dx[] = { 0, 1, 0, -1};
int dy[] = { 1, 0, -1, 0};

double dist( double x1, double y1, double x2, double y2 )
{
    return (double)(sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) ));
}

double sum(double xx, double yy)
{
    int i;
    double s = 0, d;
    for(i = 1;i <= n; i++)
    {
        d = dist(xx, yy, x[i], y[i]);
        s = s + dist(xx, yy, x[i], y[i]);
    }
    return s;
}


int main()
{
    ifstream fin("adapost2.in");
    ofstream fout("adapost2.out");

    fin>>n;

    for( i = 1; i<= n; i++ )
        fin>>x[i]>>y[i];

    double j=100;

    x_sol = x[1];
    y_sol = y[1];
    sol = sum(x[1], y[1]);

    while(j > 0.0001)
    {
        for(i = 0; i < 4; i++)
        {
            xx = x_sol + j*dx[i];
            yy = y_sol + j*dy[i];
            sol_aux = sum(xx, yy);

            if(sol_aux < sol)
            {
                sol = sol_aux;
                x_sol = xx;
                y_sol = yy;
                i = 10;
            }
        }
        if( i<10 )
            j /= 2.0;
    }

    fout<<x_sol<<" "<<y_sol;

    return 0;
}