Pagini recente » Cod sursa (job #1877688) | Cod sursa (job #81166) | Cod sursa (job #1224021) | Cod sursa (job #733743) | Cod sursa (job #2025359)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
int i,j,n,l[1000001],k;
double S;
struct pn{int i,j;} a[100001];
bool ss(pn A,pn B)
{
if(A.i>B.i)return 0;
if(A.i==B.i&&A.j>B.j)return 0;
return 1;
}
void di(int b,int e)
{
if(e-b<4)
{
double s=0;
int t1,t2;
for(i=b;i<e;++i)for(j=i+1;j<=e;++j)
{
t1=a[i].i-a[j].i;t2=a[i].j-a[j].j;
s=(float)sqrt(t1*t1+t2*t2);
if (s<S)S=s;
}
}
else
{
int m=(e+b)/2;int cm=a[m].i+1;
di(b,m);di(m+1,e);
int b1=m,e1=m,s=2*S;
while(a[b1].i>=cm-s)b1--;
while(a[e1].i<=cm+s)e1--;
int t1,t2;
for(i=b1;i<=m;++i)for(j=m+1;j<=e1;++j)
{
t1=a[i].i-a[j].i;t2=a[i].j-a[j].j;
s=(float)sqrt(t1*t1+t2*t2);
if (s<S)S=s;
}
}
}
int main()
{
f>>n;
for(i=1;i<=n;i++)f>>a[i].i>>a[i].j;
sort(a+1,a+n+1,ss);
S=(float)sqrt((a[1].i-a[2].i)*(a[1].i-a[2].i)+(a[1].j-a[2].j)*(a[1].j-a[2].j));
di(1,n);
i=S;
g<<i<<'.';
i=(S-i)*1000000;
g<<i/100000<<(i/10000)%10<<(i/1000)%10<<(i/100)%10<<(i/10)%10<<i%10;
}