Pagini recente » Cod sursa (job #1286814) | Cod sursa (job #3291251) | Cod sursa (job #2764966) | Cod sursa (job #2327091) | Cod sursa (job #956265)
Cod sursa(job #956265)
#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
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;
}
cout << P.x << " " << P.y;
}
int main()
{
freopen ("adapost2.in", "r", stdin);
freopen ("adapost2.out", "w", stdout);
int i;
scanf ("%d", &N);
for (i = 1; i <= N; i ++){
scanf ("%lf %lf", &V[i].x, &V[i].y);
X += V[i].x;
Y += V[i].y;
}
X /= N;
Y /= N;
Solve ();
return 0;
}