Pagini recente » Cod sursa (job #472595) | Cod sursa (job #1441831) | Cod sursa (job #951919) | Cod sursa (job #2854090) | Cod sursa (job #1035792)
#include <cmath>
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
struct Point {double x, y;};
ifstream fin("adapost2.in");
ofstream fout("adapost2.out");
const double EPSILON = 1e-3;
int N;
vector<Point> points;
Point result;
Point CG;
void hill_climbing();
inline double dist_sum(Point p);
inline double squared_dist(Point A, Point B);
int main() {
fin >> N;
points.resize(N);
for (int i = 0; i < N; ++i) {
fin >> points[i].x >> points[i].y;
CG.x += points[i].x;
CG.y += points[i].y;
}
CG.x /= N;
CG.y /= N;
hill_climbing();
fout << result.x << ' ' << result.y;
}
void hill_climbing() {
result = CG;
double so_far = dist_sum(result);
double cover = 256;
bool improved = true;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
while (cover > EPSILON) {
improved = false;
for (int k = 0; k < 4; ++k) {
Point p = {result.x + dx[k] * cover, result.y + dy[k] * cover};
double tot_dist = dist_sum(p);
if (tot_dist < so_far) {
so_far = tot_dist;
improved = true;
result = p;
break;
}
}
if (!improved) {
cover /= 2;
}
}
}
inline double dist_sum(Point p) {
double result = 0;
for (auto x : points) {
result += squared_dist(p, x);
}
return result;
}
inline double squared_dist(Point A, Point B) {
double result = 0;
result += (A.x - B.x) * (A.x - B.x);
result += (A.y - B.y) * (A.y - B.y);
return sqrt(result);
}