Cod sursa(job #2541572)

Utilizator memecoinMeme Coin memecoin Data 8 februarie 2020 16:39:13
Problema Adapost 2 Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.55 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.00000001

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;
}

Point solPoint;

double solve(Point p, double step) {
    
    double sol = eval(p);
    
    double dx[4] = {step, -step, 0, 0};
    double dy[4] = {0,0, step, -step};
    
    for (int k = 0; k < 4; ++k) {
        double candidate = eval({p.x + dx[k], p.y + dy[k]});
     
        if (candidate < sol && abs(candidate - sol) >= EPS) {
            return solve({p.x + dx[k], p.y + dy[k]}, step);
        }
    }
    
    if (step < EPS) {
        solPoint = p;
        return sol;
    }
    
    return solve(p, step / 2);
}

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;
    
    solve(p, 1000);
    
    fout << solPoint.x << " " << solPoint.y;
    
    return 0;
}