Cod sursa(job #2103972)

Utilizator adascaluAlexandru Dascalu adascalu Data 10 ianuarie 2018 23:43:49
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <math.h>
#include <fstream>

using namespace std;

#define INPUT  "adapost2.in"
#define OUTPUT "adapost2.out"
#define Nmax 50001
double v[Nmax][2],field,x,y,best;

int n;
fstream in, out;
 
double distance(double x1, double y1, double x2, double y2) {
    double a,b;
    a = x1 - x2;
    b = y1 - y2;
    return sqrt ( a * a + b * b );
}
 
int checkSolution(double x, double y) {
    double tot;
    int i;
    tot = 0.0;
    for (i = 1; i <= n; ++i)
        tot += distance (v[i][0], v[i][1], x, y);
     
    if (tot<best) {
        best=tot; return 1;
    }
 
    return 0;
}
 
void search() {
 
    if (checkSolution(x - field, y)) {
        x -= field;
        search();
        return ;
    }
 
    if (checkSolution(x, y - field)) {
        y -= field;
        search();
        return ;
    }
     
    if (checkSolution(x + field, y)) {
        x += field;
        search();
        return ;
    }
 
    if (checkSolution(x, y + field)) {
        y += field;
        search();
        return ;
    }

    field/=10.0;
 
    if (field<0.0001)
        return;
    else
        search();
}
 
int main() {
    int i;

    in.open(INPUT, std::ios_base::in);
    out.open(OUTPUT, std::ios_base::out);

    in >> n;
     
    for (i = 1; i <= n; ++i)
        in >> v[i][0] >> v[i][1];
    best=100000000000000.0;
 
    field=100.0;
 
    search();
 
    out << x << " " << y << endl;

    in.close();
    out.close();
    return 0;
}