Cod sursa(job #2792500)

Utilizator game_difficultyCalin Crangus game_difficulty Data 1 noiembrie 2021 19:47:00
Problema Adapost 2 Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.82 kb
#include <fstream>
#include <cmath>

using namespace std;

ifstream cin("adapost2.in");
ofstream cout("adapost2.out");

struct Point {
    double x, y;
    Point operator+ (Point other) {
        return { x + other.x, y + other.y };
    }
    void operator+= (Point other) {
        x += other.x;
        y += other.y;
    }
    Point operator/ (double other) {
        return { x / other, y / other };
    }
    void operator/= (double other) {
        x /= other;
        y /= other;
    }
    Point operator* (double other) {
        return { x * other, y * other };
    }
    void operator*= (double other) {
        x *= other;
        y *= other;
    }
};
istream& operator>> (istream& stream, Point p) {
    stream >> p.x >> p.y;
    return stream;
}
ostream& operator<< (ostream& stream, Point p) {
    stream << p.x << ' ' << p.y;
    return stream;
}

Point dir[] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };
Point soldati[50005];
int n;

double dist(Point p1, Point p2) {
    double x = abs(p1.x - p2.x), y = abs(p1.y - p2.y);
    return sqrt(x * x + y * y);
}
double findDist(Point p) {
    double distTotal = 0;
    for (int i = 1; i <= n; i++) {
        distTotal += dist(p, soldati[i]);
    }
    return distTotal;
}

int main()
{
    cin >> n;
    Point ans = { 0, 0 };
    for (int i = 1; i <= n; i++) {
        cin >> soldati[i].x >> soldati[i].y;
        ans += soldati[i];
    }
    ans /= n;
    double minDist = findDist(ans);
    double distStep = 1024;
    while (distStep > 0.001) {
        for (int i = 0; i < 4; i++) {
            double x = findDist(ans + dir[i] * distStep);
            if (x < minDist) {
                minDist = x;
                ans += dir[i] * distStep;
            }
        }
        distStep /= 2;
    }
    cout << ans;
    return 0;
}