Cod sursa(job #2073345)

Utilizator DarianCDarian Craciun DarianC Data 22 noiembrie 2017 23:22:04
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>
using namespace std;

const int Nmax = 100005;
int N;

struct Point
{
    int x, y;
} P[Nmax], V[Nmax];

long long minD = 4e18; // store it as LL and get the sqrt after (better performance)

bool smallerX(const Point& p1, const Point& p2) { return (p1.x < p2.x); }
bool smallerY(const Point& p1, const Point& p2) { return (p1.y < p2.y); }

long long dist(const Point& p1, const Point& p2)
{
    int dx = p2.x - p1.x,
        dy = p2.y - p1.y;
    return (1LL * dx * dx) + (1LL * dy * dy);
}


void read()
{
    ifstream fin("cmap.in");
    fin >> N;
    for(int i = 0; i < N; i++)
        fin >> P[i].x >> P[i].y;
    fin.close();
}

void print_sol()
{
    ofstream fout("cmap.out");
    fout << fixed << setprecision(6) << sqrt(minD) << '\n';
    fout.close();
}

void find_closest(int L, int R)
{
    if(R - L == 1)
    {
        minD = min(minD, dist(P[L], P[L+1]));
        return;
    }

    int M = (L + R)/2;
    int sepx = P[M].x;

    find_closest(L, M);
    find_closest(M, R);

    merge(P+L, P+M, P+M, P+R, V, smallerY);
    int k = 0;
    for(int i = L; i <= R; i++)
        if(abs(P[i].x - sepx) < minD)
            V[k++] = P[i];

    for(int i = 0; i < (k - 1); i++)
        for(int j = (i + 1); j < min(k, i + 8); j++)
            minD = min(minD, dist(V[i], V[j]));

}

int main()
{
    read();
    sort(P, P+N, smallerX);
    find_closest(0, N-1);
    print_sol();
    return 0;
}