Pagini recente » Cod sursa (job #2861669) | Cod sursa (job #2143883) | Cod sursa (job #2067175) | Cod sursa (job #1035783) | Cod sursa (job #956262)
Cod sursa(job #956262)
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
ifstream in ("adapost2.in");
ofstream out ("adapost2.out");
const double EPS = 1e-5;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
struct point
{
double x, y;
};
int N;
point V[50010];
double X, Y;
inline double dist (const point &A, const point &B)
{
return double (sqrt ((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y)));
}
inline double total_dist (const point &X)
{
double ret = 0;
int i;
for (i = 1; i <= N; i ++)
ret += dist (X, V[i]);
return ret;
}
void Solve ()
{
point P = {X, Y};
double best = total_dist (P), now;
double step = 512.0;
bool ok;
int i;
while (step > EPS){
ok = 0;
for (i = 0; i < 4; i ++){
point S = {P.x + step * dx[i], P.y + step * dy[i]};
now = total_dist (S);
if (now < best){
best = now;
P = S;
ok = 1;
break;
}
}
if (!ok)
step /= 2.0;
}
out << P.x << " " << P.y;
}
int main()
{
int i;
in >> N;
for (i = 1; i <= N; i ++){
in >> V[i].x >> V[i].y;
X += V[i].x;
Y += V[i].y;
}
X /= N;
Y /= N;
Solve ();
return 0;
}