Cod sursa(job #1735981)

Utilizator refugiatBoni Daniel Stefan refugiat Data 31 iulie 2016 19:26:10
Problema Suma si numarul divizorilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define punct pair<int,int>
#define x first
#define y second
#define inf 999999999999999
using namespace std;
FILE*si=fopen("cmap.in","r");
FILE*so=fopen("cmap.out","w");
punct v[100005];
punct aux[100005];
bool comp(punct a,punct b)
{
    if(a.y<b.y)
        return true;
    if(a.y==b.y)
        return (a.x<b.x);
    return false;
}
inline long long dist(punct a,punct b)
{
    return (1LL*(a.x-b.x)*(a.x-b.x)+1LL*(a.y-b.y)*(a.y-b.y));
}
long long cmap(int st,int dr)
{
    if(st==dr)
        return inf;
    if(st==dr-1)
        return dist(v[st],v[dr]);
    int mid=(st+dr)>>1;
    int midx=v[mid].x;
    long long dmin=min(cmap(st,mid),cmap(mid+1,dr));
    merge(v+st,v+mid+1,v+mid+1,v+dr+1,aux,comp);
    int i;
    for(i=st;i<=dr;++i)
    {
        v[i]=aux[i-st];
    }
    int s=0;
    for(i=st;i<=dr;++i)
    {
        if(1LL*abs((v[i].x-midx))*abs((v[i].x-midx))<=dmin)
            aux[s++]=v[i];
    }
    int j;
    for(i=0;i<s;++i)
    {
        for(j=i+1;j<s;++j)
        {
            if(1LL*(aux[j].y-aux[i].y)*(aux[j].y-aux[i].y)<=dmin)
                dmin=min(dmin,dist(aux[j],aux[i]));
        }
    }
    return dmin;
}
int main()
{
    int n;
    fscanf(si,"%i",&n);
    int i;
    for(i=1;i<=n;++i)
    {
        fscanf(si,"%i %i",&v[i].x,&v[i].y);
    }
    sort(v+1,v+n+1);
    fprintf(so,"%.6f",sqrt(cmap(1,n)));
    fclose(so);
    return 0;
}