Pagini recente » Cod sursa (job #2273589) | Cod sursa (job #177148) | Cod sursa (job #2741858) | Cod sursa (job #1689534) | Cod sursa (job #1644484)
#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;
}