Cod sursa(job #2557639)

Utilizator Alin_StanciuStanciu Alin Alin_Stanciu Data 25 februarie 2020 21:58:54
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.76 kb
#include <iostream>
#include <fstream>
#include <map>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

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

using PI = pair<int, int>;

int n;
pair<int, int> A[100001];
map<pair<int, int>, vector<int>> M;

bool Divide(int l, bool jos, bool dr) // jos, dr - offset de L / 2 la impartire? Returneaza true daca exista 2 puncte in acelasi patrat
{
    bool gasit = false;
    M.clear();
    for (int i = 1; i <= n; ++i)
    {
        int x = A[i].first, y = A[i].second;
        if (jos) x += l / 2;
        if (dr) y += l / 2;
        x /= l, y /= l;
        M[{x, y}].push_back(i);
        if (M[{x, y}].size() >= 2)
            gasit = true;
    }
    return gasit;
}

int Cb() // Returneaza cea mai mica latura l pentru care la impartirea in patrate de l sa existe cel putin doua puncte in acelasi patrat
{
    int st = 1, dr = 2000000001;
    while (st <= dr)
    {
        int mij = st / 2 + dr / 2;
        if (st % 2 == 1 && dr % 2 == 1)
            ++mij;\
        bool gasit = false;
        for (bool jos : {false, true})
        {
            for (bool drp : {false, true})
            {
                if (Divide(mij, jos, drp))
                {
                    dr = mij - 1;
                    gasit = true;
                    break;
                }
            }
            if (gasit)
                break;
        }
        if (!gasit)
            st = mij + 1;
    }
    return st;
}

int main()
{
    fin >> n;
    for (int i = 1; i <= n; ++i)
    {
        int x, y;
        fin >> y >> x;
        A[i] = {x + 1000000000, y + 1000000000};
    }
    int l = Cb();
    Divide(l, false, false);
    double dmin = 3000000000.0d;
    for (auto& p : M)
    {
        int x = p.first.first, y = p.first.second;
        for (int dx = 0; dx <= 2; ++dx)
        {
            for (int dy = 0; dy <= 2; ++dy)
            {
                pair<int, int> p2(x + dx, y + dy);
                if (M.find(p2) != M.end())
                {
                    for (int el1 : p.second)
                    {
                        for (int el2 : M[p2])
                        {
                            if (el1 != el2)
                            {
                                int c1 = (A[el1].first - A[el2].first) * (A[el1].first - A[el2].first);
                                int c2 = (A[el1].second - A[el2].second) * (A[el1].second - A[el2].second);
                                dmin = min(dmin, sqrt(1.0d * c1 + 1.0d * c2));
                            }
                        }
                    }
                }
            }
        }
    }
    fout << fixed << setprecision(6) << dmin;

    return 0;
}