Pagini recente » Cod sursa (job #1258456) | Cod sursa (job #1608846) | Cod sursa (job #3030843) | Cod sursa (job #2015916) | Cod sursa (job #1101768)
// hill climbing
#include <fstream>
#include <cmath>
#include <iostream>
#define EPS 0.0001
using namespace std;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int NMax = 50010;
struct punct
{
double x, y;
punct() {x = y = 0.0;}
punct(const double x, const double y)
{
this -> x = x;
this -> y = y;
}
};
punct ans, a[NMax] ;
int n;
void Read()
{
ifstream f ("adapost2.in");
f>>n;
for (int i = 1; i <= n; ++i)
{
double x, y; f>>x>>y;
a[i] = punct(x, y);
}
f.close();
}
inline double sqr(const double &x)
{
return x * x;
}
inline double GetDist(const punct &now)
{
double ret = 0;
for (int i = 1; i<=n; ++i)
ret += sqrt(sqr(now.x-a[i].x)+sqr(now.y-a[i].y));
return ret;
}
inline void Solve()
{
punct G, now, cpy;
for (int i = 1; i<=n; ++i)
G.x += a[i].x, G.y += a[i].y;
G.x /= n, G.y /= n;
now = G;
double dist = GetDist(G);
for (double ratio = 64.0; ratio >= EPS; ratio /= 2)
{
bool modif = false;
for (int k = 0; k < 4; ++k)
{
now.x = G.x + dx[k]*ratio;
now.y = G.y + dy[k]*ratio;
double distnow = GetDist(now);
if (distnow < dist)
{
modif = true;
dist = distnow;
G = now;
}
}
if (modif)
{
ratio *= 2;
}
}
ans = G;
}
void Write()
{
freopen("adapost2.out", "w", stdout);
printf("%.4lf %.4lf\n", ans.x, ans.y);
}
int main()
{
Read();
Solve();
Write();
return 0;
}