Cod sursa(job #2557677)

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

using namespace std;

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

struct Punct
{
    int x, y;

    bool operator < (const Punct& other) const
    {
        if (y == other.y)
            return x < other.x;
        return y < other.y;
    }
};

int n;
Punct A[100001];
map<Punct, 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].x, y = A[i].y;
        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 >> x >> y;
        A[i] = {x + 1000000000, y + 1000000000};
    }
    int l = Cb();
    Divide(l, false, false);
    double dmin = 3000000000.0d;
    for (const pair<Punct, vector<int>>& patrat : M)
    {
        const Punct& p = patrat.first;
        const vector<int>& El = patrat.second;
        for (int dx = 0; dx <= 2; ++dx)
        {
            for (int dy = 0; dy <= 2; ++dy)
            {
                Punct p2 = {p.x + dx, p.y + dy}; // pozitia patratului vecin
                if (M.find(p2) != M.end())
                {
                    for (int el1 : El)
                    {
                        for (int el2 : M[p2])
                        {
                            if (el1 != el2)
                            {
                                int c1 = (A[el1].x - A[el2].x) * (A[el1].x - A[el2].x);
                                int c2 = (A[el1].y - A[el2].y) * (A[el1].y - A[el2].y);
                                dmin = min(dmin, sqrt(1.0d * c1 + 1.0d * c2));
                            }
                        }
                    }
                }
            }
        }
    }
    fout << fixed << setprecision(6) << dmin;

    return 0;
}