Cod sursa(job #2166062)

Utilizator PopeangaMihneaPopeanga Mihnea- Stefan PopeangaMihnea Data 13 martie 2018 15:22:44
Problema Cele mai apropiate puncte din plan Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <bits/stdc++.h>

using namespace std;

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

struct punct
{
    double x, y;
}p[100001];

int n;

double dist(punct a, punct b)
{
    return sqrt((b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y));
}

bool cmp(punct a, punct b)
{
    return (a.x<b.x)||(a.x==b.x && a.y<b.y);
}

double closestStrip(int strip[], int n, double d)
{
    double ans=d;
    sort(strip+1, strip+n+1);
    for(int i=1; i<=n; ++i)
    {
        for(int j=i+1; j<=n; ++j)
        {
            if(p[strip[j]].y-p[strip[i]].y>=d) break;
            ans=min(ans, dist(p[strip[i]], p[strip[j]]));
        }
    }
    return ans;
}

double divide(int st, int dr)
{
    if(dr-st<2)
    {
        double answer=2e9 + 2;
        for(int i=st; i<dr; ++i)
        {
            for(int j=i+1; j<=dr; ++j)
            {
                answer=min(answer, dist(p[i], p[j]));
            }
        }
        return answer;
    }
    int m=(st+dr)/2;
    double d=divide(st, m);
    d=min(d, divide(m+1, dr));
    int strip[100001];
    int j=0;
    for(int i=st; i<=dr; ++i)
    {
        if(abs(p[m].x-p[i].x)<2)
        {
            ++j;
            strip[j]=i;
        }
    }
    return min(d, closestStrip(strip, j, d));
}

int main()
{
    fin>>n;
    for(int i=1; i<=n; ++i) fin>>p[i].x>>p[i].y;
    sort(p+1, p+n+1, cmp);
    fout<<fixed<<divide(1, n);
    return 0;
}