Cod sursa(job #3214157)

Utilizator alexandru_ioan.06Alexandru Ioan alexandru_ioan.06 Data 13 martie 2024 20:46:50
Problema Cele mai apropiate puncte din plan Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <bits/stdc++.h>

using namespace std;

struct punct
{
    int l , c;
}a[100001];

long double dist (punct a , punct b)
{
    int x = a.l - b.l , y = a.c - b.c;
    return sqrt(x * x + y * y);
}

bool cmp1 (punct a , punct b)
{
    if(a.c != b.c)
        return (a.c < b.c);
    return (a.l < b.l);
}

bool cmp (punct a , punct b)
{
    if(a.l != b.l)
        return a.l < b.l;
    return a.c < b.c;
}

long double DIE (int l , int r)
{
    if(r - l + 1 <= 3)
    {
        long double ans = 1e9;
        for (int i = l; i <= r; ++i)
            for (int j = i + 1; j <= r; ++j)
                ans = min(ans , dist(a[i] , a[j]));
        return ans;
    }
    else
    {
        int m = (l + r) / 2;
        long double A = DIE (l , m);
        long double B = DIE (m + 1 , r);
        long double dMin = min(A , B);
        vector <punct> x;
        for (int i = l; i <= r; ++i)
            if(abs(a[i].l - a[m].l) <= dMin)
                x.push_back(a[i]);
        sort (x.begin() , x.end() , cmp1);
        for(int i = 0; i < (int)x.size(); ++i)
            for (int j = i + 1; j < (int)x.size() && j - i + 1 <= 8; ++j)
                dMin = min(dMin , dist(x[i] , x[j]));
        return dMin;
    }
}

int main()
{
    ifstream fin ("cmap.in");
    ofstream fout ("cmap.out");
    int N;
    fin >> N;
    for(int i = 1; i <= N; ++i)
        fin >> a[i].l >> a[i].c;
    sort(a + 1 , a + N + 1 , cmp);
    fout << fixed << setprecision(7) << DIE(1 , N);
}