Cod sursa(job #1510075)

Utilizator sebinechitasebi nechita sebinechita Data 24 octombrie 2015 15:43:27
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.07 kb
#include <fstream>
#include <limits.h>
#include <iostream>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream fi("cmap.in");
ofstream fo("cmap.out");
#define MAX 100100
#define INF 2000000000
struct Point{
    int x, y;
} p[MAX], y[MAX];
int n;
typedef long long ld;

ld dist(Point a, Point b)
{
    return 1ll * (a.x - b.x) * (a.x - b.x) + 1ll * (a.y - b.y) * (a.y - b.y);
}

inline bool cmp(Point a, Point b)
{
    return a.x < b.x;
}

ld closest(int st, int dr)
{
    if(st == dr - 1)
        return dist(p[dr], p[st]);
    int mij = (st + dr) / 2;
    ld delta;
    if(st == mij)
        delta = closest(mij + 1, dr);
    else if(mij + 1 == dr)
        delta = closest(st, mij);
    else
        delta = min(closest(st, mij), closest(mij + 1, dr));
    ld x = p[mij].x + p[mij + 1].x;
    x /= 2;
    int i = st;
    int j = mij + 1;
    int f = 0;
    while(i <= mij && j <= dr)
    {
        if(p[i].x + delta < x)
            i++;
        else if(p[j].x - delta > x)
            j++;
        else
        {
            if(p[i].y < p[j].y)
            {
                y[++f] = p[i];
                i++;
            }
            else
            {
                y[++f] = p[j];
                j++;
            }
        }
    }
    while(i <= mij)
    {
        if(p[i].x + delta >= x)
            y[++f] = p[i];
        i++;
    }
    while(j <= dr)
    {
        if(p[j].x - delta <= x)
            y[++f] = p[j];
        j++;
    }
    for(i = 1 ; i <= f ; i++)
    {
        for(j = i + 1 ; j - i >= 7 && j <= f ; j++)
        {
            if(y[j].y - delta > y[i].y)
                break;
            if(dist(y[i], y[j]) < delta)
                delta = dist(y[i], y[j]);
        }
    }
    return delta;
}


int main()
{
    fi >> n;
    for(int i = 1 ; i <= n ; i++)
    {
        fi >> p[i].x >> p[i].y;
    }
    sort(p + 1, p + n + 1, cmp);
    fo << fixed << setprecision(6) << sqrt(closest(1, n)) << "\n";

    fi.close();
    fo.close();
    return 0;
}