Cod sursa(job #2657426)

Utilizator VladOSBVlad Oleksik VladOSB Data 10 octombrie 2020 15:39:26
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.75 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>

using namespace std;

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

int n,a[100002][2],i,j;

long double dist(int x, int y)
{
    long long x1=a[x][0];
    long long x2=a[y][0];
    long long y1=a[x][1];
    long long y2=a[y][1];
    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][0]+a[mij+1][0])/2;
    long double Smin=0.0;
    Smin=cmap(st,mij);
    Smin=min(Smin,cmap(mij+1,dr));
    int xmin=vert-Smin;
    int xmax=vert+Smin;
    int st1=st;
    int dr1=dr;
    int mij1;
    while(st1<=dr1)
    {
        mij1=(st1+dr1)/2;
        if(a[mij1][0]<xmin)
        {
            st1=mij1+1;
        }
        else
        {
            if(a[mij1][0]>xmin)
            {
                dr1=mij1-1;
            }
            else
            {
                while(a[mij1][0]==xmin)
                {
                    mij1--;
                }
                mij1++;
                break;
            }
        }
    }
    int indminx;
    if(st1>dr1)
    {
        if(st1<=st)
            indminx=st1;
        else
            indminx=n+1;
    }
    else
    {
        indminx=mij1;
    }
    st1=st;
    dr1=dr;
    while(st1<=dr1)
    {
        mij1=(st1+dr1)/2;
        if(a[mij1][0]<xmax)
        {
            st1=mij1+1;
        }
        else
        {
            if(a[mij1][0]>xmax)
            {
                dr1=mij1-1;
            }
            else
            {
                while(a[mij1][0]==xmax)
                {
                    mij1--;
                }
                mij1++;
                break;
            }
        }
    }
    int indmaxx;
    if(st1>dr1)
    {
        if(dr1>=dr)
            indmaxx=dr1;
        else
            indmaxx=0;
    }
    else
    {
        indmaxx=mij1;
    }
    int b[dr-st+3][2];
    int p=0;
    for(i=indminx;i<=indmaxx;i++)
    {
        b[p][0]=a[i][0];
        b[p++][1]=a[i][1];
    }
    for(i=0;i<p;i++)
    {
        for(j=i+1;j<p+8;j++)
        {
            if(sqrt((b[i][0]-b[j][0])*(b[i][0]-b[j][0])+(b[i][1]-b[j][1])*(b[i][1]-b[j][1]))<Smin)
            {
                Smin=sqrt((b[i][0]-b[j][0])*(b[i][0]-b[j][0])+(b[i][1]-b[j][1])*(b[i][1]-b[j][1]));
            }
        }
    }
    //cout << "REZULTAT PTR: " << st << ' ' << dr << " : " << Smin << '\n';
    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);
}

int main()
{
    in >> n;
    for(i=0;i<n;i++)
    {
        in >> a[i][0] >> a[i][1];
    }
    sortare_x(0,n-1);
    /*for(i=10000;i<10002;i++)
    {
        cout << a[i][0] << ' ' << a[i][1] << '\n';
    }*/
    long double l=cmap(0,n-1);
    out << fixed << setprecision(6) << l;
}