Cod sursa(job #2659911)

Utilizator VladOSBVlad Oleksik VladOSB Data 17 octombrie 2020 19:25:48
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.66 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>

using namespace std;

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

struct punct{long long x, y;};
punct a[100002],b[100002];

int n,i,j;

bool compy(punct a,punct b)
{
    if(a.y<b.y)
        return 1;
    if(a.y==b.y)
    {
        if(a.x<b.x)
            return 1;
    }
    return 0;
}

long double dist(int x, int y)
{
    long long x1=a[x].x;
    long long x2=a[y].x;
    long long y1=a[x].y;
    long long y2=a[y].y;
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

long double cmap(int st,int dr)
{
    //cout << "SE RULEAZA: " << st << ' ' << dr << '\n';
    if(dr-st<3)
    {
        long double S=1000000000.0;
        for(int m=st;m<=dr;m++)
        {
            for(int p=m+1;p<=dr;p++)
            {
                long double d=dist(p,m);
                if(d<S)
                {
                    S=d;
                }
            }
        }
        //cout << "REZULTAT PTR: " << st << ' ' << dr << " : " << S << '\n';
        return S;
    }
    int mij=(st+dr)/2;
    int vert=a[mij].x;
    long double Smin=0.0;
    Smin=cmap(st,mij);
    Smin=min(Smin,cmap(mij+1,dr));
    int ps,pd;
    for(ps=mij;ps>=st;ps--)
    {
        if(vert-a[ps].x>=Smin)
        {
            break;
        }
    }
    ps++;
    for(pd=mij;pd<=dr;pd++)
    {
        if(a[pd].x-vert>=Smin)
        {
            break;
        }
    }
    pd--;
    for(int i=ps;i<=pd;i++)
    {
        b[i]=a[i];
    }
    sort(b+ps,b+pd+1,compy);
    for(int i=ps;i<pd;i++)
    {
        for(int j=i+1;j<=min(i+7,pd);j++)
        {
            if(dist(i,j)<Smin)
            {
                Smin=dist(i,j);
            }
        }
    }
    return Smin;
}

/*int partitionare(int st, int dr)
{
    int i=st,j=dr,s=1;
    while(i<j)
    {
        if(a[i][0]>a[j][0])
        {
            swap(a[i][0],a[j][0]);
            swap(a[i][1],a[j][1]);
            s=-s;
        }
        if(s==1)
            i++;
        else
            j--;
    }
    return i;
}

void sortare_x(int st, int dr)
{
    if(st>=dr)
        return;
    int p=partitionare(st,dr);
    sortare_x(st,p-1);
    sortare_x(p+1,dr);
}*/

bool compx(punct a,punct b)
{
    if(a.x<b.x)
        return 1;
    if(a.x==b.x)
    {
        if(a.y<b.y)
            return 1;
    }
    return 0;
}



int main()
{
    in >> n;
    for(i=0;i<n;i++)
    {
        in >> a[i].x >> a[i].y;
    }
    //sortare_x(0,n-1);
    sort(a,a+n,compx);
    long double l=cmap(0,n-1);
    out << fixed << setprecision(6) << l;
}