Cod sursa(job #1026941)

Utilizator costel93FMI - Dumea Eduard Constantin costel93 Data 12 noiembrie 2013 11:59:47
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.17 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <iomanip>

using namespace std;
struct punct
{
    int x,y;
} v[100005],ax;

int n1,n,i,p,s,i1;

double calc(int a,int b)
{
    double dist;
    double ax1,ax2;
    ax1=v[a].x-v[b].x;
    ax1=ax1*ax1;
    ax2=v[a].y-v[b].y;
    ax2=ax2*ax2;
    dist=sqrt(ax1+ax2);
    return dist;
}

double dei(int st, int dr)
{
    if (dr-st==1)
    {
        double dist;
        dist=calc(st,dr);
        return dist;
    }
    if (dr-st==2)
    {
        double dist1,dist2,dist3;
        dist1=calc(st,st+1);
        dist2=calc(st,dr);
        dist3=calc(dr-1,dr);
        return min(min(dist1,dist2),dist3);
    }
    double distl,distr,dist;
    int mij = (st+dr)/2;
	
    distl=dei(st,mij);
    distr=dei(mij+1,dr);
    dist=min(distl,distr);
	
    int dr1,st1;
    st1=v[mij].x-dist;
    dr1=v[mij].x+dist;
    while (v[st].x<st1)
        st++;
    while (v[dr].x>dr1)
        dr--;
    int i,j;
    for (i=st;i<dr;i++)
        for (j=i+1;((j<=dr)||(j<=i+7));j++)
            dist=min(dist,calc(i,j));
    return dist;
}
int verificare(int s)
{
    if (2*s>n1)
        return 0;
    if (2*s+1<=n1)
    {
        if (max(v[s].x,max(v[s*2].x,v[s*2+1].x))==v[s].x)
            return 0;
        if (v[s*2].x>v[s*2+1].x)
            return s*2;
        return s*2+1;
    }
    if (max(v[s].x,v[s*2].x)==v[s].x)
        return 0;
    return s*2;
}
int main(void)
{
    ifstream fin("cmap.in");
    ofstream fout("cmap.out");
    
	fin>>n;
	
    for (i=1;i<=n;i++)
    {
        fin>>v[i].x>>v[i].y;
        p=i;
        while ((p>1)&&(v[p/2].x<v[p].x))
        {
            ax=v[p];
            v[p]=v[p/2];
            v[p/2]=ax;
            p=p/2;
        }
    }
    n1=n;
    for (i=1;i<=n;i++)
    {
        ax=v[n1];
        v[n1]=v[1];
        v[1]=ax;
        n1--;
        s=1;
        p=verificare(s);
        while (p!=0)
        {
            ax=v[s];
            v[s]=v[p];
            v[p]=ax;
            s=p;
            p=verificare(s);
        }
    }
    fout<<setiosflags(ios::fixed)<<setprecision(7)<<dei(1,n);
   
    return 0;
}