Cod sursa(job #2934461)

Utilizator MihaiZ777MihaiZ MihaiZ777 Data 6 noiembrie 2022 00:41:13
Problema Adapost 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <fstream>
#include <iostream>
#include <math.h>
using namespace std;

ifstream fin("adapost2.in");
ofstream fout("adapost2.out");

int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

struct vec2 {
    double x, y;
};
int n;
vec2 soldiers[50000];

double ComputeLenSum(double x, double y) {
    double sum = 0;
    for (int i = 0; i < n; i++) {
        double deltaX = x - soldiers[i].x;
        double deltaY = y - soldiers[i].y;

        sum += sqrt(deltaX * deltaX + deltaY * deltaY);
    }
    return sum;
}

int main() {
    fin >> n;

    double sumX = 0, sumY = 0;

    for (int i = 0; i < n; i++) {
        double x, y;
        fin >> x >> y;
        sumX += x;
        sumY += y;
        soldiers[i] = {x, y};
    }

    double currX = sumX / n;
    double currY = sumY / n;
    cout << currX << ' ' << currY;

    double minDist = ComputeLenSum(currX, currY);

    double posX;
    double posY;
    for (double eps = 1000; eps > 0.001; ) {
        bool shouldAdvance = false;

        for (int i = 0; i < 4; i++) {
            posX = currX + eps * dir[i][0];
            posY = currY + eps * dir[i][1];
            double dist = ComputeLenSum(posX, posY);

            if (dist < minDist) {
                minDist = dist;
                currX = posX;
                currY = posY;
                shouldAdvance = true;
            }
        }
        if (!shouldAdvance) {
            eps /= 2;
        }
    }

    fout.setf(ios::fixed, ios::floatfield);
    fout.precision(4);
    fout << currX << ' ' << currY << '\n';
}