Cod sursa(job #2082623)

Utilizator andreiiiiPopa Andrei andreiiii Data 6 decembrie 2017 16:58:42
Problema Adapost 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 kb
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <algorithm>
#include <fstream>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <vector>
using namespace std;

double x[50011];
double y[50011];

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

    int n;
    fin >> n;
    int m = n;
    if (n % 4 != 0) {
        m -= m % 4;
        m += 4;
    }

    double cx = 0, cy = 0;
    for (int i = 0; i < n; ++i) {
        fin >> x[i] >> y[i];
        cx += x[i];
        cy += y[i];
    }
    cx /= n; cy /= n;

    auto getValue = [n, m](double vx, double vy) -> double {
        double ans = 0;
        for (int i = n; i < m; ++i) {
            x[i] = vx;
            y[i] = vy;
        }
        for (int i = 0; i < n; i += 4) {
            ans += sqrt((vx - x[i]) * (vx - x[i]) + (vy - y[i]) * (vy - y[i]));
            ans += sqrt((vx - x[i + 1]) * (vx - x[i + 1]) + (vy - y[i + 1]) * (vy - y[i + 1]));
            ans += sqrt((vx - x[i + 2]) * (vx - x[i + 2]) + (vy - y[i + 2]) * (vy - y[i + 2]));
            ans += sqrt((vx - x[i + 3]) * (vx - x[i + 3]) + (vy - y[i + 3]) * (vy - y[i + 3]));
        }
        return ans;
    };

    const int dx[] = {-1, -1, 0, 1, 1, 0};
    const int dy[] = {0, 1, 1, 0, -1, -1};

    double coef = 300;
    double dist = getValue(cx, cy);
    int lim = 30;
    if (n <= 10000) {
        lim = 40;
    }
    for (int it = 0; it < lim; ++it) {
        int dir = -1;
        double minDist = 1e99;
        for (int i = 0; i < 6; ++i) {
            double nx = cx + dx[i] * coef;
            double ny = cy + dy[i] * coef;
            double cDist = getValue(nx, ny);
            if (cDist < minDist) {
                minDist = cDist;
                dir = i;
            }
        }
        if (minDist < dist) {
            dist = minDist;
            cx += dx[dir] * coef;
            cy += dy[dir] * coef;
        }
        coef *= 0.6;
    }

    fout << setprecision(4) << fixed;
    fout << cx << ' ' << cy << '\n';



    fin.close();
    fout.close();
}