Pagini recente » Cod sursa (job #1987196) | Cod sursa (job #165688) | Cod sursa (job #833348) | Cod sursa (job #124255) | Cod sursa (job #2793168)
#include <fstream>
#include <cmath>
using namespace std;
ifstream cin("adapost2.in");
ofstream cout("adapost2.out");
struct Point {
int x, y;
Point operator+ (Point other) {
return { x + other.x, y + other.y };
}
void operator+= (Point other) {
x += other.x;
y += other.y;
}
Point operator/ (int other) {
return { x / other, y / other };
}
void operator/= (int other) {
x /= other;
y /= other;
}
Point operator* (int other) {
return { x * other, y * other };
}
void operator*= (int other) {
x *= other;
y *= other;
}
};
istream& operator>> (istream& stream, Point p) {
stream >> p.x >> p.y;
return stream;
}
ostream& operator<< (ostream& stream, Point p) {
double x = p.x / 1000.f, y = p.y / 1000.f;
stream << x << ' ' << y;
return stream;
}
Point dir[] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };
Point soldati[50005];
int n;
double dist(Point p1, Point p2) {
double x = abs(p1.x - p2.x), y = abs(p1.y - p2.y);
return sqrt(x * x + y * y);
}
double findDist(Point p) {
double distTotal = 0;
for (int i = 1; i <= n; i++) {
distTotal += dist(p, soldati[i]);
}
return distTotal;
}
int main()
{
cin >> n;
Point ans = { 0, 0 };
for (int i = 1; i <= n; i++) {
double x, y;
cin >> x >> y;
soldati[i].x = x * 1000;
soldati[i].y = y * 1000;
ans += soldati[i];
}
ans /= n;
double minDist = findDist(ans);
int distStep = 2 << 18;
while (distStep > 1) {
bool ok = false;
for (int i = 0; i < 4; i++) {
double x = findDist(ans + dir[i] * distStep);
if (x < minDist) {
ok = true;
minDist = x;
ans += dir[i] * distStep;
}
}
if(!ok)
distStep /= 2;
}
cout << ans;
return 0;
}