Cod sursa(job #2969528)

Utilizator Zed1YasuoAlex Birsan Zed1Yasuo Data 23 ianuarie 2023 12:48:44
Problema Cele mai apropiate puncte din plan Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.36 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <vector>
#define lr long double
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
int n;
const int N=1e5+3;
struct pct
{
    int x,y;
}a[N];
int b[N];
bool comp(pct X,pct Y)
{
    if(X.x==Y.x)
        return X.y<Y.y;
    return X.x<Y.x;
}
lr dist(pct X,pct Y)
{
    return sqrt((X.x-Y.x)*(X.x-Y.x)+(X.y-Y.y)*(X.y-Y.y));
}
lr calc(int st,int dr)
{
    if(dr-st+1<=3)
    {
        lr mn=1e12;
        for(int i=st;i<=dr;i++)
            for(int j=i+1;j<=dr;j++)
                mn=min(mn,dist(a[i],a[j]));
        for(int i=st;i<=dr;i++)
            for(int j=i+1;j<=dr;j++)
                if(a[i].y>a[j].y)
                    swap(a[i],a[j]);
        return mn;
    }
    else
    {
        int mj=(st+dr)/2;
        lr as=a[mj].x;
        lr dst=calc(st,mj);
        lr ddr=calc(mj+1,dr);
        lr dmin=min(dst,ddr);
        vector<pct>b;
        vector<pct>c;
        for(int i=st;i<=mj;i++)
            if(abs(a[i].x-as)<=dmin)
                b.push_back(a[i]);
        int s1=b.size()-1;
        for(int i=mj+1;i<=dr;i++)
            if(abs(a[i].x-as)<=dmin)
                b.push_back(a[i]);
        int p1=0;
        int p2=s1+1;
        int s2=b.size()-1;
        while(p1<=s1&&p2<=s2)
        {
            if(abs(b[p1].x-as)<=abs(b[p2].x-as))
                c.push_back(b[p1]),p1++;
            else
                c.push_back(b[p2]),p2++;
        }
        while(p1<=s1)
            c.push_back(b[p1]),p1++;
        while(p2<=s2)
            c.push_back(b[p2]),p2++;
        for(int i=0;i<c.size();i++)
            for(int w=1;w<=7&&w+i<c.size();w++)
                dmin=min(dmin,dist(c[i],c[i+w]));
        b.clear();
        p1=st;
        p2=mj+1;
        while(p1<=mj&&p2<=dr)
        {
            if(a[p1].y<a[p2].y)
                b.push_back(a[p1]),p1++;
            else
                b.push_back(a[p2]),p2++;
        }
        while(p1<=mj)
            b.push_back(a[p1]),p1++;
        while(p2<=dr)
            b.push_back(a[p2]),p2++;
        for(int i=st;i<=dr;i++)
            a[i]=b[i-st];
        return dmin;
    }
}
int main()
{
    f>>n;
    for(int i=1;i<=n;i++)
        f>>a[i].x>>a[i].y;
    sort(a+1,a+n+1,comp);
    g<<fixed<<setprecision(8)<<calc(1,n);
    return 0;
}