Cod sursa(job #2411546)

Utilizator petru.ciocirlanPetru Ciocirlan petru.ciocirlan Data 20 aprilie 2019 20:53:00
Problema Cele mai apropiate puncte din plan Scor 35
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.61 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;

set < int > 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;
}

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

    sort(Vect, Vect + N);

    long long minDist = INF;
    Arg.insert(0);
    int st = 0; /// go from the left i guess??
    for(int i = 1; i < N; ++i)
    {
        while(coordDist(Vect[st], Vect[i]) >= minDist)
        {
            Arg.erase(st);
            ++st;
        }

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

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

    return 0;
}