Cod sursa(job #2233138)

Utilizator Laura_CorneiLaura Maria Cornei Laura_Cornei Data 22 august 2018 13:39:56
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.99 kb
#include <bits/stdc++.h>
#define nmax 100005
#define ll long long
using namespace std;
fstream f1("cmap.in", ios::in);
fstream f2("cmap.out", ios::out);
int n;
ll rez=4000000000000000000;
struct punct
{
    ll x, y;
}p[nmax], py[nmax], aux[nmax];
bool cmp1(punct a, punct b)
{
    return a.x< b.x;
}
bool cmp2(punct a, punct b)
{
    return a.y> b.y;
}
ll dist(punct a, punct b) ///dist^2
{
    return (a.x-b.x)*(a.x-b.x)+ (a.y-b.y)*(a.y-b.y);
}
void citire()
{
    f1>>n;
    for(int i=1; i<=n; i++)
        f1>>p[i].x>>p[i].y;
    sort(p+1, p+n+1, cmp1);
}
void brut(int st, int dr)
{
    ll val;
    if(dr-st+1==1) return;
    for(int i=st; i<=dr; i++)
        for(int j=i+1; j<=dr; j++)
        {
            val=dist(p[i], p[j]);
            if(rez> val)
               rez=val;
        }
     for(int i=st; i<=dr; i++)
         py[i]=p[i];
     sort(py+st, py+dr+1, cmp2);
}
void interclasare(int st, int mijl, int dr)
{
    int i=st, j=mijl+1, k=0;
    while((i<=mijl)&&(j<=dr))
    {
        if(py[i].y>py[j].y) {k++; aux[k]=py[i]; i++;}
        else {k++; aux[k]=py[j]; j++;}
    }
    while(i<=mijl)
    {
        k++; aux[k]=py[i]; i++;
    }
    while(j<=dr)
    {
        k++; aux[k]=py[j]; j++;
    }
    for(j=1, i=st; j<=k; j++,i++)
        py[i]=aux[j];
}
void mij(int st, int mijl, int dr)
{
    ll val;
    int k=0;
    for(int i=st; i<=dr; i++)
        if(abs(py[i].x-py[mijl].x)<=rez)
    {
        k++; aux[k]=py[i];
    }
    for(int i=st; i<=dr; i++)
        for(int j=i+1; (j<=dr)&&(j-i)<=8; j++)
    {
        val=dist(py[i], py[j]);
        if(val< rez) rez=val;
    }
}
void solutie(int st, int dr)
{
    if(dr-st+1<=3) brut(st, dr);
    else
    {
        int mijl=(st+dr)/2;
        solutie(st, mijl);
        solutie(mijl+1, dr);
        interclasare(st, mijl, dr);
        mij(st, mijl, dr);
    }
}
int main()
{
    citire();
    solutie(1, n);
    f2<<fixed<<setprecision(10)<<sqrt(rez);
    return 0;
}