Cod sursa(job #2411582)

Utilizator petru.ciocirlanPetru Ciocirlan petru.ciocirlan Data 20 aprilie 2019 21:23:03
Problema Cele mai apropiate puncte din plan Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.12 kb
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <set>
using namespace std;

#define FILE_NAME "cmap"
ifstream in (FILE_NAME".in");
ofstream out(FILE_NAME".out");

struct punct
{
    int x, y;
    punct(int _x = 0, int _y = 0)
    {
        x = _x;
        y = _y;
    }
    bool operator<(punct operand)
    {
        if(this->x == operand.x)
            return this->y < operand.y;
        return this->x < operand.x;
    }
};

constexpr long long INF = 0x3f3f3f3f3f3f3f3f;
constexpr int MAX_DIM = 100000 + 4;
punct Vect[MAX_DIM];
int N;

struct comp
{
    bool operator()(const int &a, const int &b)
    {
        if(Vect[a].y == Vect[b].y)
            return Vect[a].x < Vect[b].x;
        return Vect[a].y < Vect[b].y;
    }
};

set < int, comp > Arg;

inline
long long coordDist(punct A, punct B)
{
    long long distX = A.x - B.x;
    distX *= distX;
    long long distY = A.y - B.y;
    distY *= distY;
    return distX + distY;
}

inline
long long square(long long a)
{
    return a * a;
}

int main()
{
    in >> N;
    for(int i = 0; i < N; ++i)
        in >> Vect[i].x >> Vect[i].y;

    sort(Vect, Vect + N);

    int st = 0; /// go from the left i guess??
    long long minDist = coordDist(Vect[0], Vect[1]);
    Arg.insert(0); Arg.insert(1);
    for(int i = 2; i < N; ++i)
    {
        while(square(Vect[i].x - Vect[st].x) > minDist)
        {
            Arg.erase(st);
            ++st;
        }
/*
        auto Iter = Arg.begin();
        while(Iter != Arg.end() && square(Vect[i].y - Vect[*Iter].y) > minDist)
            Iter = Arg.erase(Iter);*/

        for(auto dot = Arg.begin(); dot != Arg.end(); ++dot)
        {
            long long dist = coordDist(Vect[*dot], Vect[i]);
            if(minDist > dist)
                minDist = dist;
            /*if(square(Vect[i].y - Vect[*dot].y) > minDist)
            {
                dot = Arg.erase(dot);
                --dot;
            }*/
        }

        Arg.insert(i);
    }

    out << fixed << setprecision(6) << sqrt(minDist) << '\n';

    return 0;
}