Pagini recente » Cod sursa (job #1870144) | Cod sursa (job #1274766) | Cod sursa (job #531043) | Istoria paginii runda/sadsf | Cod sursa (job #1253840)
#include <fstream>
#include <iomanip>
#include <cmath>
using namespace std;
const int kMaxN = 50005;
ifstream fin("adapost2.in");
ofstream fout("adapost2.out");
int N;
double px[kMaxN], py[kMaxN], dmin = 1000000006.9, step = 250.0, x, y;
inline double Dist(double x1, double y1, double x2, double y2) {
double dx = x1 - x2, dy = y1 - y2;
return sqrt(dx * dx + dy * dy);
}
bool Check(double nx, double ny) {
double crt = 0.0;
for (int i = 0; i < N; ++i)
crt += Dist(nx, ny, px[i], py[i]);
if (crt < dmin) {
dmin = crt;
x = nx;
y = ny;
return true;
}
return false;
}
int main() {
fin >> N;
for (int i = 0; i < N; ++i)
fin >> px[i] >> py[i];
Check(500.0, 500.0);
int stmax = N < 10000 ? 75 : 30;
for (int i = 0; i < stmax; ++i, step /= 2) {
if (!Check(x + step, y))
Check(x - step, y);
if (!Check(x, y + step))
Check(x, y - step);
}
fout << setprecision(4) << fixed << x << " " << y << "\n";
return 0;
}