Cod sursa(job #1769365)

Utilizator dranoellenTurica Leonard-Petru dranoellen Data 2 octombrie 2016 14:03:07
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.5 kb
#include <iostream>
#include <fstream>
#include <limits.h>
#include <algorithm>
#include <math.h>
#define MLen 100005
using namespace std;
ofstream fout("cmap.out");
ifstream fin ("cmap.in");
struct tip
{
    int x, y;
} pct[MLen],sec[MLen];
int iy[MLen],n,aux[MLen];
long long rasp=LLONG_MAX;

long long minim(long long a, long long b)
{
    if(a<b)return a;return b;
}
long long dist(tip a,tip b)
{
    int x=a.x-b.x, y=a.y-b.y;
    return ((long long)((x*x)+(y*y)));
}

// interclasari pe x si y
void interc(int st, int m, int dr)
{
    int i=st, j=m+1,k=st;
    while(k<=dr)
    {
        if((i<=m)&&(pct[i].x<=pct[j].x))
            sec[k++]=pct[i++];

        if((j<=dr)&&(pct[j].x<=pct[i].x))
            sec[k++]=pct[j++];

        if(i>m)while(j<=dr)sec[k++]=pct[j++];
        if(j>dr) while(i<=m)sec[k++]=pct[i++];
    }
    for(k=st; k<=dr; ++k)pct[k]=sec[k];

}

void intercy(int st, int m, int dr)
{
    int i=st, j=m+1,k=st;
    while(k<=dr)
    {
        if((i<=m)&&(pct[iy[i]].y<=pct[iy[j]].y))
            aux[k++]=iy[i++];

        if((j<=dr)&&(pct[iy[j]].y<=pct[iy[i]].y))
            aux[k++]=iy[j++];

        if(i>m)while(j<=dr)aux[k++]=iy[j++];
        if(j>dr) while(i<=m)aux[k++]=iy[i++];
    }
    for(k=st; k<=dr; ++k)iy[k]=aux[k];

}

// sortare pe x si y
void srt(int st, int dr)
{
    int m=(st+dr)/2;
    if(st<dr)
    {
        srt(st,m);
        srt(m+1,dr);
        interc(st,m,dr);
    }
    return;
}

void srty(int st, int dr)
{
    int m=(st+dr)/2;
    if(st<dr)
    {
        srty(st,m);
        srty(m+1,dr);
        intercy(st,m,dr);
    }
    return;
}

void genesa (int st, int dr)
{

    int m=(st+dr)/2,l=pct[m].x;
    if(dr-st<3)
    {
        for(int i=st;i<dr; ++i)
            for(int j=i+1; j<=dr; ++j)
            {
                long long h=dist(pct[i],pct[j]);
                rasp=minim(rasp,h);
            }
            return;
    }
    genesa (st, m);
    genesa (m+1,dr);
    int k=st;
    for(int i=st; i<=dr; ++i)
    {
        if((long long)(pct[i].x-l)*(pct[i].x-l)<rasp)iy[k++]=i;
    }
    k--;
    srty(st,k);
    for(int i=st;i<k;i++)
        for(int j=i+1;j<=k&&j<=i+8;j++)
        {
            long long h=dist(pct[iy[i]],pct[iy[j]]);
            rasp=minim(rasp,h);
        }
}

int main()
{
    fin>>n;
    for(int i=0; i<n; ++i)fin>>pct[i].x>>pct[i].y,iy[i]=i;
    srt(0,n-1);
    for(int i=0;i<n;i++)

    genesa(0,n-1);
    fout<<sqrt(rasp);
    return 0;
}