Cod sursa(job #2642743)

Utilizator PatrickCplusplusPatrick Kristian Ondreovici PatrickCplusplus Data 17 august 2020 01:50:39
Problema Cele mai apropiate puncte din plan Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.28 kb
#include <bits/stdc++.h>

using namespace std;

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

const int nmax = 100000;
const long long inf = 9223372036854775807;
int n;

struct Point
{
    long long x, y;
}v[nmax + 5], y[nmax + 5], aux[nmax + 5];

bool cmp(Point a, Point b)
{
    if (a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}

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

void interclaseaza(int st, int dr)
{
    int mid = (st + dr) / 2;
    int p1 = st, p2 = mid + 1, p3 = st;
    while (p1 <= mid && p2 <= dr)
    {
        if (y[p1].y < y[p2].y)
        {
            aux[p3++] = y[p1++];
        }
        else
        {
            aux[p3++] = y[p2++];
        }
    }
    while (p1 <= mid)
    {
        aux[p3++] = y[p1++];
    }
    while (p2 <= dr)
    {
        aux[p3++] = y[p2++];
    }
    for (int i = st; i <= dr; ++i)
    {
        y[i] = aux[i];
    }
}

long long solve(int st, int dr)
{
    if (dr - st + 1 <= 3)
    {
        interclaseaza(st, dr);
        if (dr - st + 1 == 3)
        {
            long long minim = dist(v[st], v[st + 1]);
            minim = min(minim, dist(v[st], v[dr]));
            minim = min(minim, dist(v[st + 1], v[dr]));
            return minim;
        }
        if (dr - st + 1 == 1)
        {
            return inf;
        }
        return dist(v[st], v[dr]);
    }
    int mid = (st + dr) / 2;
    int x = v[mid].x;
    long long minim = min(solve(st, mid), solve(mid + 1, dr));
    interclaseaza(st, dr);
    int p3 = 0;
    for (int i = st; i <= dr; ++i)
    {
        if (1LL * abs(y[i].x - x) * abs(y[i].x - x) <= minim)
        {
            aux[++p3] = y[i];
        }
    }
    for (int i = 1; i < p3; ++i)
    {
        for (int j = i + 1; j - i + 1 <= 8 && j <= p3; ++j)
        {
            minim = min(minim, dist(y[i], y[j]));
        }
    }
    return minim;
}

int main()
{
    fin >> n;
    for (int i = 1; i <= n; ++i)
    {
        fin >> v[i].x >> v[i].y;
        y[i] = v[i];
    }
    sort(v + 1, v + n + 1, cmp);
    fout << setprecision(6)<< fixed << (double)sqrt(solve(1,n));
    fin.close();
    fout.close();
    return 0;
}