Cod sursa(job #2278996)

Utilizator mihaicivMihai Vlad mihaiciv Data 8 noiembrie 2018 20:02:53
Problema Adapost 2 Scor 94
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <iostream>
#include <fstream>
#include <cmath>
#define DMIN 0.001
using namespace std;

ifstream f("adapost2.in");
ofstream g("adapost2.out");

struct Punct {
    double x, y;
}p[50003];

double dx[] = {100.0, -100.0, 0.0, 0.0};
double dy[] = {0.0, 0.0, 100.0, -100.0};

int n;

double findDistance(Punct p1) {
    double dist = 0;
    for (int i = 0; i < n; ++i) {
        dist = dist + ( sqrt( (p[i].x - p1.x) * (p[i].x - p1.x) + (p[i].y - p1.y) * (p[i].y - p1.y) ) );
    }
    return dist;
}

Punct cautare(Punct p1, double dist) {
    if (dist <= DMIN) {
        return p1;
    } else {
        double current_distance = findDistance(p1);
        Punct paux;
        bool found = false;
        for (int i = 0; i < 4 && !found; ++i) {
            paux.x = p1.x + dx[i];
            paux.y = p1.y + dy[i];
            if ( findDistance(paux) < current_distance ) {
                return cautare(paux, dist);
                found = true;
            }
        }
        if (!found) {
            for (int i = 0; i < 4; ++i) {
                dx[i] = dx[i] / 2.0;
                dy[i] = dy[i] / 2.0;
            }
            return cautare(p1, dist / 2.0);
        }

    }
}

int main() {

    f >> n;

    double Sx = 0.0;
    double Sy = 0.0;

    for (int i = 0; i < n; ++i) {
        f >> p[i].x >> p[i].y;
        Sx = (Sx + p[i].x);
        Sy = (Sy + p[i].y);
    }

    double initialDistance = 30.0;
    Punct startP;
    startP.x = Sx / n;
    startP.y = Sy / n;

    Punct answer = cautare(startP, initialDistance);
    g << answer.x << " " << answer.y;
    return 0;
}