Pagini recente » Monitorul de evaluare | Profil M@2Te4i | Monitorul de evaluare | Cod sursa (job #1127918) | Cod sursa (job #2017162)
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>
#include <climits>
#include <queue>
#include <ctime>
using namespace std;
typedef long long LL;
#ifdef INFOARENA
#define ProblemName "adapost2"
#endif
#define MCONCAT(A, B) A B
#ifdef ProblemName
#define InFile MCONCAT(ProblemName, ".in")
#define OuFile MCONCAT(ProblemName, ".out")
#else
#define InFile "fis.in"
#define OuFile "fis.out"
#endif
const int MAXN = 50000;
int N;
double x[MAXN], y[MAXN];
clock_t t0;
double dst(double ax, double ay, double bx, double by) {
double dx = ax - bx, dy = ay - by;
return sqrt(dx * dx + dy * dy);
}
double eval(double ex, double ey) {
double ans = 0.0;
for (int i = 0; i < N; ++i)
ans += dst(ex, ey, x[i], y[i]);
return ans;
}
double rand01() {
return ((double)rand()) / RAND_MAX;
}
double getCurrentTime() {
return (double)(clock() - t0) / CLOCKS_PER_SEC;
}
const double MAXC = 1100;
double bx, by, best;
void relax(double cx, double cy) {
double cand = eval(cx, cy);
if (cand < best) {
best = cand;
bx = cx, by = cy;
}
}
int main() {
t0 = clock();
srand(12547);
assert(freopen(InFile, "r", stdin));
assert(freopen(OuFile, "w", stdout));
scanf("%d", &N);
for (int i = 0; i < N; ++i)
scanf("%lf %lf", &x[i], &y[i]);
bx = 0.0, by = 0.0; best = eval(bx, by);
double t = 1.0; const double factor = 0.99997;
while (getCurrentTime() <= 0.19) {
double dx = MAXC * rand01() * t, dy = MAXC * rand01() * t;
relax(bx + dx, by + dy); relax(bx - dx, by + dy);
relax(bx + dx, by - dy); relax(bx - dx, by - dy);
t *= factor;
}
//fprintf(stderr, "%.8lf\n", t);
printf("%.8lf %.8lf\n", bx, by);
return 0;
}