Pagini recente » Cod sursa (job #2144331) | Cod sursa (job #179759) | Cod sursa (job #2105569) | Cod sursa (job #1883571) | Cod sursa (job #1292380)
//
// main.cpp
// timus_1815
//
// Created by Alexandru Andronache on 14/12/14.
// Copyright (c) 2014 Alexandru Andronache. All rights reserved.
//
// http://en.wikipedia.org/wiki/Simulated_annealing
#include <iostream>
#include <cmath>
using namespace std;
const int POINTS = 50001;
const double EPSILON = 0.0001;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
struct point
{
double x, y;
};
point p[POINTS];
int N;
double originX = 0, originY = 0;
double newX = 0, newY = 0, newD = 0;
double minX, maxX, minY, maxY;
FILE *f = fopen("adapost2.in", "r");
FILE *g = fopen("adapost2.out", "w");
double dist(double x, double y)
{
double rez = 0, dx = 0, dy = 0;
for (int i = 0; i < N; ++i)
{
dx = p[i].x - x;
dy = p[i].y - y;
rez += sqrt(dx * dx + dy * dy);
}
return rez;
}
int main(int argc, const char * argv[])
{
minX = 1000, maxX = -1000, minY = 1000, maxY = -1000;
fscanf(f, "%d", &N);
for (int i = 0; i < N; ++i)
{
fscanf(f, "%lf %lf", &p[i].x, &p[i].y);
minX = min(minX, p[i].x);
minY = min(minY, p[i].y);
maxX = max(maxX, p[i].x);
maxY = max(maxY, p[i].y);
}
originX = originY = 0;
for (int i = 0; i < N; ++i)
{
originX += p[i].x;
originY += p[i].y;
}
originX = originX / POINTS;
originY = originY / POINTS;
double d = dist(originX, originY);
double s = max(maxX - minX, maxY - minY);
while (s > EPSILON)
{
bool move = false;
for ( int i = 0; i < 4; ++i )
{
newX = originX + s * dx[i];
newY = originY + s * dy[i];
newD = dist(newX, newY);
if (newD < d)
{
originX = newX;
originY = newY;
d = newD;
move = true;
break;
}
}
if (!move) s = s / 2;
}
fprintf(g, "%.4lf %.4lf\n", originX, originY);
return 0;
}