Cod sursa(job #2541577)

Utilizator memecoinMeme Coin memecoin Data 8 februarie 2020 16:45:08
Problema Adapost 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <fstream>
#include <string>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#include <map>
#include <string.h>
#include <queue>
#include <stack>

#define INF 0x3f3f3f3f

using namespace std;

#ifdef DEBUG
string name = "data";
#else
string name = "adapost2";
#endif

ifstream fin(name + ".in");
ofstream fout(name + ".out");

int n;

struct Point {
    double x,y;
};

#define MAXN 50005
#define EPS 0.001

Point points[MAXN];

double eval(Point &p) {
    double sol = 0;
    
    for (int i = 0; i < n; ++i) {
        sol += sqrt((points[i].x - p.x) * (points[i].x - p.x) + (points[i].y - p.y) * (points[i].y - p.y));
    }
    
    return sol;
}

int main() {
    
    Point p = {0,0};
    
    fin >> n;
    
    for (int i = 0; i < n; ++i) {
        double x, y;
        fin >> x >> y;
        
        points[i] = {x, y};
        
        p.x += x;
        p.y += y;
    }
    
    p.x /= n;
    p.y /= n;
    
    double sol = eval(p);
    double step = 1000;
    
    while (true) {
        if (step < EPS) {
            break;
        }
        
        double dx[4] = {step, -step, 0, 0};
        double dy[4] = {0,0, step, -step};
        
        double candidate = INF;
        
        for (int k = 0; k < 4; ++k) {
            p.x += dx[k];
            p.y += dy[k];
            candidate = eval(p);
            
            if (candidate < sol) {
                break;
            }
            p.x -= dx[k];
            p.y -= dy[k];
        }
        
        if (candidate < sol) {
            sol = candidate;
        } else {
            step /= 2;
        }
    }
    
    fout << p.x << " " << p.y;
    
    return 0;
}