Cod sursa(job #1644484)

Utilizator 2dorTudor Ciurca 2dor Data 9 martie 2016 23:38:11
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.24 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
using namespace std;

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


class Point {
  public:
    double x;
    double y;

    Point(double x, double y) {
        this->x = x;
        this->y = y;
    }

    Point() {
        this->x = 0;
        this->y = 0;
    }
};

int N; // number of points
vector<Point> points;
Point current_point;
int dx[] = { 0,  1,  0, -1};
int dy[] = {-1,  0,  1,  0};

// Magnitude of the step
double epsilon = 100;
// Number of iterations after which the computation should settle
const int ITERATIONS = 40;

void ReadData() {
    fin >> N;
    double x, y;
    for (int i = 0; i < N; ++i) {
        fin >> x >> y;
        points.push_back(Point(x, y));
        current_point.x += x;
        current_point.y += y;
    }
}

double FitnessFunction(Point relative_point) {
    double result = 0.0;
    double difference_x, difference_y;
    for (Point point : points) {
        difference_x = point.x - relative_point.x;
        difference_y = point.y - relative_point.y;
        result += sqrt(difference_x * difference_x + difference_y * difference_y);
    }
    return result;
}

void Solve() {
    // Compute the median point
    current_point.x /= N;
    current_point.y /= N;
    double current_best_fitness = FitnessFunction(current_point);
    double next_fitness_function;
    bool updated;
    Point next_point;
    for (int i = 0; i < ITERATIONS; ++i) {
        updated = false;
        for (int k = 0; k < 4; ++k) {
            next_point.x = current_point.x + epsilon * dx[k];
            next_point.y = current_point.y + epsilon * dy[k];
            next_fitness_function = FitnessFunction(next_point);
            // When we find a new best fitness value, we go in that direction
            if (current_best_fitness > next_fitness_function) {
                current_best_fitness = next_fitness_function;
                current_point = next_point;
                updated = true;
                break;
            }
        }
        if (!updated) {
            epsilon /= 2;
        }
    }
}

void WriteAnswer() {
    fout << current_point.x << ' ' << current_point.y << '\n';
}

int main() {
    ReadData();
    Solve();
    WriteAnswer();
    return 0;
}