Cod sursa(job #978972)

Utilizator Daniel3717Aleca Daniel Adrian Daniel3717 Data 30 iulie 2013 20:04:25
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.12 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;
    dist=sqrt(((v[a].x-v[b].x)*(v[a].x-v[b].x))+((v[a].y-v[b].y)*(v[a].y-v[b].y)));
    return dist;
}
double dei(int l, int r)
{
    if (r-l==1)
    {
        double dist;
        dist=calc(l,r);
        return dist;
    }
    if (r-l==2)
    {
        double dist1,dist2,dist3;
        dist1=calc(l,l+1);
        dist2=calc(l,r);
        dist3=calc(r-1,r);
        return min(min(dist1,dist2),dist3);
    }
    double distl,distr,dist;
    int mij;
    mij=(l+r)/2;
    distl=dei(l,mij);
    distr=dei(mij+1,r);
    dist=min(distl,distr);
    int ll,rr;
    ll=v[mij].x-dist;
    rr=v[mij].x+dist;
    while (v[l].x<ll)
        l++;
    while (v[r].x<rr)
        r--;
    int i,j;
    for (i=l;i<r;i++)
        for (j=i+1;((j<=r)||(j<=i+7));j++)
            dist=min(dist,calc(i,j));
    return dist;
}
int godown(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)
{
    FILE * f;
    f=fopen("cmap.in","r");
    ofstream g("cmap.out");
    fscanf(f,"%d",&n);
    for (i=1;i<=n;i++)
    {
        fscanf(f,"%d%d",&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=godown(s);
        while (p!=0)
        {
            ax=v[s];
            v[s]=v[p];
            v[p]=ax;
            s=p;
            p=godown(s);
        }
    }
    g<<setiosflags(ios::fixed)<<setprecision(7)<<dei(1,n);
    g.close();
    return 0;
}