Pagini recente » Cod sursa (job #1031995) | Cod sursa (job #87264) | Cod sursa (job #2779754) | Cod sursa (job #1496984) | Cod sursa (job #2541572)
#include <fstream>
#include <string>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#include <map>
#include <string.h>
#include <queue>
#include <stack>
#define INF 0x3f3f3f3f
using namespace std;
#ifdef DEBUG
string name = "data";
#else
string name = "adapost2";
#endif
ifstream fin(name + ".in");
ofstream fout(name + ".out");
int n;
struct Point {
double x,y;
};
#define MAXN 50005
#define EPS 0.00000001
Point points[MAXN];
double eval(Point p) {
double sol = 0;
for (int i = 0; i < n; ++i) {
sol += sqrt((points[i].x - p.x) * (points[i].x - p.x) + (points[i].y - p.y) * (points[i].y - p.y));
}
return sol;
}
Point solPoint;
double solve(Point p, double step) {
double sol = eval(p);
double dx[4] = {step, -step, 0, 0};
double dy[4] = {0,0, step, -step};
for (int k = 0; k < 4; ++k) {
double candidate = eval({p.x + dx[k], p.y + dy[k]});
if (candidate < sol && abs(candidate - sol) >= EPS) {
return solve({p.x + dx[k], p.y + dy[k]}, step);
}
}
if (step < EPS) {
solPoint = p;
return sol;
}
return solve(p, step / 2);
}
int main() {
Point p = {0,0};
fin >> n;
for (int i = 0; i < n; ++i) {
double x, y;
fin >> x >> y;
points[i] = {x, y};
p.x += x;
p.y += y;
}
p.x /= n;
p.y /= n;
solve(p, 1000);
fout << solPoint.x << " " << solPoint.y;
return 0;
}