Cod sursa(job #1984735)

Utilizator borcanirobertBorcani Robert borcanirobert Data 25 mai 2017 19:34:04
Problema Cele mai apropiate puncte din plan Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.85 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <vector>
using namespace std;

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

const int MAX = 100005;
struct Point{
    int x, y;

    bool operator < ( const Point& a ) const
    {
        return x < a.x;
    }
};
using LL = long long;
vector<Point> a;
int N;
double dmin;

void Read();
LL Dist_Min( int st, int dr );
LL Dist( Point a, Point b );

LL Mod( LL x )
{
    if ( x >= 0 )
        return x;
    return -x;
}

bool Comp( const Point& x, const Point& y )
{
    return x.y < y.y || ( x.y == y.y && x.x < y.x );
}

int main()
{
    Read();
    LL r = Dist_Min(0, a.size() - 1);
    dmin = sqrt(r);

    fout << fixed << setprecision(6) << dmin << '\n';

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

void Read()
{
    fin >> N;
    int x, y, i;
    for ( i = 1; i <= N; ++i )
    {
        fin >> x >> y;
        a.push_back({x, y});
    }

    sort( a.begin(), a.end() );
}

LL Dist_Min( int st, int dr )
{
    if ( dr - st + 1 <= 3 )
    {
        if ( dr - st + 1 == 2 )
            return Dist(a[st], a[dr]);
        return min( min( Dist(a[st], a[st + 1]), Dist(a[st], a[st + 2]) ), Dist(a[st + 1], a[st + 2]) );
    }

    int mij = ( st + dr ) / 2;
    LL s1 = Dist_Min(st, mij);
    LL s2 = Dist_Min(mij + 1, dr);
    LL sc = min(s1, s2);

    vector<Point> P;
    for ( int i = st; i <= dr; ++i )
        if ( Mod(a[mij].x - a[i].x) <= sc )
            P.push_back(a[i]);

    sort(P.begin(), P.end(), Comp);

    for ( size_t i = 0; i < P.size(); ++i )
        for ( size_t j = i + 1; j < P.size() && j - i >= 7; ++j )
        {
            int dist = Dist(P[i], P[j]);
            if ( dist < sc )
                sc = dist;
        }

    return sc;
}

LL Dist( Point a, Point b )
{
    return 1LL*( a.x - b.x )*( a.x - b.x ) + 1LL*( a.y - b.y )*( a.y - b.y );
}