Cod sursa(job #1292380)

Utilizator alex23alexandru andronache alex23 Data 14 decembrie 2014 11:38:51
Problema Adapost 2 Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.02 kb
//
//  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;
}