Cod sursa(job #1775737)

Utilizator dranoellenTurica Leonard-Petru dranoellen Data 10 octombrie 2016 17:46:32
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.55 kb
#include <limits.h>
#include <algorithm>
#include <math.h>
#include <iomanip>
#include <cstdio>
#define MLen 100005
using namespace std;
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)
            {

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


            rasp=minim(rasp,dist(pct[iy[i]],pct[iy[j]]));
        }
}

int main()
{
    FILE *in=fopen("cmap.in","r"),*out=fopen("cmap.out","w");
    fscanf (in, "%d",&n);

    for(int i=0; i<n; ++i)
    {
        fscanf(in,"%d%d",&pct[i].x,&pct[i].y);
        iy[i]=i;
    }
    srt(0,n-1);
    for(int i=0; i<n; i++)
        genesa(0,n-1);
        fprintf(out, "%.7f",sqrt(rasp));
    return 0;
}