Cod sursa(job #2046182)

Utilizator retrogradLucian Bicsi retrograd Data 23 octombrie 2017 15:31:19
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <bits/stdc++.h>

using namespace std;

struct Point { double x, y; };

template<typename Func>
pair<double, Point> HillClimb(Point p, Func func) {
    double best = func(p);
    for (double step = 1000; step > 5e-4; step *= 0.4)
        for (int it = 0; it < 1; ++it)
            for (int dx = -1; dx <= 1; ++dx)
                for (int dy = -1; dy <= 1; ++dy) {
                    Point q = p; q.x += dx * step; q.y += dy * step;
                    double now = func(q);
                    if (best > now) { best = now; p = q; } // (*)
                }
    return make_pair(best, p);
}

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

    int n; cin >> n;
    vector<Point> points(n);
    for (int i = 0; i < n; ++i) {
        cin >> points[i].x >> points[i].y;
    }

    auto ret = HillClimb(Point{500, 500}, [&](Point& p) {
        double ret = 0; 
        for (int i = 0; i < n; ++i) {
            double dx = p.x - points[i].x;
            double dy = p.y - points[i].y;
            ret += sqrt(dx * dx + dy * dy + 1e-9);
        }
        return ret;
    }).second;

    cout << fixed << setprecision(20);
    cout << ret.x << " " << ret.y << endl;

    return 0;
}