Cod sursa(job #2669717)

Utilizator VladOSBVlad Oleksik VladOSB Data 7 noiembrie 2020 18:40:02
Problema Cele mai apropiate puncte din plan Scor 85
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.71 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(punct v1[], int x, punct v2[], int y)
{
    long long x1=v1[x].x;
    long long x2=v2[y].x;
    long long y1=v1[x].y;
    long long y2=v2[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(a,p,a,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=mij+1;i<=pd;i++)
    {
        b[i]=a[i];
    }
    sort(b+mij+1,b+pd+1,compy);
    for(int i=ps;i<=mij;i++)
    {
        int poz;
        poz=upper_bound(b+mij+1,b+pd+1,a[i],compy)-b;
        if(poz<=pd)
        {
            for(int j=poz;j<=pd;j++)
            {
                if(abs(a[i].y-b[j].y)>Smin)
                    break;
                if(dist(a,i,b,j)<Smin)
                {
                    Smin=dist(a,i,b,j);
                }
            }
            for(int j=poz;j>=mij+1;j--)
            {
                if(abs(a[i].y-b[j].y)>Smin)
                    break;
                if(dist(a,i,b,j)<Smin)
                {
                    Smin=dist(a,i,b,j);
                }
            }
        }
        /*for(int j=i+1;ct<=7;j++)
        {
            if(j>pd)
            {
                break;
            }
            if(b[i].x<=vert && b[j].x>vert)
            {
                ct++;
                if(dist(i,j)<Smin)
                {
                    Smin=dist(i,j);
                }
            }
            if(b[i].x>vert && b[j].x<=vert)
            {
                ct++;
                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;
}