Cod sursa(job #2567776)

Utilizator Rares31100Popa Rares Rares31100 Data 3 martie 2020 18:50:09
Problema Cele mai apropiate puncte din plan Scor 85
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <bits/stdc++.h>
#define PLL pair<long double,long double>
#define X first
#define Y second

using namespace std;

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

int n;
PLL pct[100001],cpy[100001];
long long Z;

long long dist(PLL a,PLL b)
{
    return (b.X-a.X)*(b.X-a.X)+(b.Y-a.Y)*(b.Y-a.Y);
}

void Find(int st,int dr)
{
    if(dr<=st)
        return;

    if(st+1==dr)
    {
        if(pct[st].Y>pct[dr].Y)
            swap(pct[st],pct[dr]);

        Z=min(Z,dist(pct[st],pct[dr]));

        return;
    }

    int mid=(st+dr)/2;

    Find(st,mid);Find(mid+1,dr);

    int p1=st,p2=mid+1;
    int poz=st;

    while(p1<=mid && p2<=dr)
        if(pct[p1].Y<=pct[p2].Y)
            cpy[poz++]=pct[p1++];
        else
            cpy[poz++]=pct[p2++];

    while(p1<=mid)
        cpy[poz++]=pct[p1++];

    while(p2<=dr)
        cpy[poz++]=pct[p2++];

    for(int i=st;i<=dr;i++)
        pct[i]=cpy[i];

    for(int i=st;i<=dr;i++)
        for(int j=i+1;j<=min(i+8,dr);j++)
            Z=min(Z,dist(pct[i],pct[j]));
}

int main()
{
    in>>n;

    for(int i=1;i<=n;i++)
        in>>pct[i].X>>pct[i].Y;

    sort(pct+1,pct+1+n);

    Z=dist(pct[1],pct[2]);

    Find(1,n);

    out<<setprecision(6)<<fixed<<sqrt(Z);

    return 0;
}