Pagini recente » Cod sursa (job #2656962) | Cod sursa (job #20625) | Cod sursa (job #1024697) | Cod sursa (job #237177) | Cod sursa (job #2541577)
#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.001
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;
}
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;
double sol = eval(p);
double step = 1000;
while (true) {
if (step < EPS) {
break;
}
double dx[4] = {step, -step, 0, 0};
double dy[4] = {0,0, step, -step};
double candidate = INF;
for (int k = 0; k < 4; ++k) {
p.x += dx[k];
p.y += dy[k];
candidate = eval(p);
if (candidate < sol) {
break;
}
p.x -= dx[k];
p.y -= dy[k];
}
if (candidate < sol) {
sol = candidate;
} else {
step /= 2;
}
}
fout << p.x << " " << p.y;
return 0;
}