Pagini recente » Cod sursa (job #515358) | Cod sursa (job #400679) | Cod sursa (job #2304439) | Cod sursa (job #1456439) | Cod sursa (job #2619603)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 50005;
const double EPS = 0.001;
int N;
pair <double, double> points[NMAX];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
double Solve(double x, double y)
{
double dist = 0;
for (int i = 1;i <= N;++i)
{
double dx = (points[i].first - x);
double dy = (points[i].second - y);
dist += sqrt(dx * dx + dy * dy);
}
return dist;
}
int main()
{
ifstream fin("adapost2.in");
ofstream fout("adapost2.out");
fin >> N;
for (int i = 1;i <= N;++i)
fin >> points[i].first >> points[i].second;
double bestx = 500, besty = 500, step = 500;
double best = Solve(bestx, besty);
while (step >= EPS)
{
for (int k = 0;k < 4;++k)
{
double nx = bestx + step * dx[k];
double ny = besty + step * dy[k];
double ndist = Solve(nx, ny);
if (ndist < best)
{
best = ndist;
bestx = nx;
besty = ny;
step *= 2;
break;
}
}
step /= 2;
}
fout << setprecision(4) << fixed;
fout << bestx << " " << besty << "\n";
fin.close();
fout.close();
return 0;
}