Cod sursa(job #1854941)

Utilizator Bodo171Bogdan Pop Bodo171 Data 23 ianuarie 2017 12:43:07
Problema Cele mai apropiate puncte din plan Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
struct point
{
    long double x,y;
}v[100005],a[100005];
bool comp1(point a,point b)
{
    return a.x<b.x;
}
bool comp2(point a,point b)
{
    return a.y<b.y;
}
int n,i,j,u,k;
long double median,ans;
long double dist(point a,point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
long double mindist(int st,int dr)
{
    if(dr-st<=2) return (1<<30);
    long double mn=(1<<30);
    int m=(st+dr)/2;
    mn=min(mindist(st,m),mindist(m+1,dr));
    median=(v[m].x+v[m+1].x)/2;
    for(i=st;i<=dr;i++)
    {
        a[i-st+1].x=v[i].x;
        a[i-st+1].y=v[i].y;
    }
    sort(a+1,a+u+1,comp2);
    u=0;
    for(i=1;i<=dr-st+1;i++)
    {
        if(fabs(v[i].x-median)<mn)
        {
            u++;
            a[u].x=a[i].x;
            a[u].y=a[i].y;
        }
    }
    j=0;
    for(i=1;i<=u;i++)
    {
        while(a[i].y-a[j].y>mn&&j<i)
            j++;
        for(k=j;k<i;k++)
            if(k!=0&&dist(a[i],a[k])<mn) mn=dist(a[i],a[k]);
    }
    return mn;
}
int main()
{
    ifstream f("cmap.in");
    ofstream g("cmap.out");
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>v[i].x>>v[i].y;
    }
    sort(v+1,v+n+1,comp1);
    ans=mindist(1,n);
    g<<fixed<<setprecision(7)<<ans;
    return 0;
}