Pagini recente » Cod sursa (job #1780396) | Cod sursa (job #543262) | Cod sursa (job #1933087) | Cod sursa (job #2453151) | Cod sursa (job #2449769)
#include<bits/stdc++.h>
#define Inf 4e18
#define nmax 1000000
using namespace std;
int n;
struct Punct
{
unsigned long long x,y;
}P[nmax];
int cmpx(Punct a,Punct b)
{
if(a.x==b.x) return 0;
return (a.x>b.x) ? 1: -1;
}
int cmpy(Punct a,Punct b)
{
if (a.y==b.y) return 0;
return (a.y>b.y) ? 1: -1;
}
float dist(Punct p1, Punct p2)
{
return ((p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y));
}
float min(float x,float y)
{
return (x<y) ? x:y;
}
float brute_force(Punct P[],int n)
{
float dmin=Inf;
for(int i=0;i<n;i++)
for( int j=i+1;j<n;j++)
if(dmin>dist(P[i],P[j]))
dmin=dist(P[i],P[j]);
return dmin;
}
int compareX(const void* a, const void* b)
{
Punct *p1 = (Punct *)a, *p2 = (Punct *)b;
if(p1->x == p2->x) return 0;
return (p1->x > p2->x) ? 1 : -1;
}
int compareY(const void* a, const void* b)
{
Punct *p1 = (Punct *)a, *p2 = (Punct *)b;
if(p1->y == p2->y) return 0;
return (p1->y > p2->y) ? 1 : -1;
}
float closest(Punct P[],int n)
{
if(n<=3) return brute_force(P,n);
else
{int mid=n/2;
Punct Pmid=P[mid];
float dl=closest(P,mid);
float dr=closest(P+mid,n-mid-1);
float d=min(dl,dr),ans=d;
Punct adj[n];
int k=0,i,j;
for(i=0;i<n;i++)
if(abs(P[i].x-Pmid.x)<=d)
adj[k++]=P[i];
//sort(adj,adj+k-1,cmpy);
//sortare2(adj,0,k-1);
qsort(adj,k,sizeof(Punct),compareY);
//cout<<adj[0].y;
//demonstrare geometrica (se construieste un cerc din varful a 5 puncte), exista maxim 5 puncte a.y. diferenta coordonatelor lor<=d
for(i=0;i<k;i++)
for(j=i+1;j<k && (adj[j].y-adj[i].y)<d;j++)
if(dist(adj[i],adj[j])<d)
d=dist(adj[i],adj[j]);
//cout<<d<<' ';
return d;
}
}
float solve()
{
//sort(P,P+n,cmpx);
//sortare(0,n-1);
qsort(P,n,sizeof(Punct),compareX);
//cout<<P[0].x;
return closest(P,n);
}
int main()
{
ifstream fin("cmap.in");
fin>>n;
for(int i=0;i<n;i++)
fin>>P[i].x>>P[i].y;
//sortare(0,n-1);
fin.close();
ofstream fout("cmap.out");
fout<<fixed<<setprecision(10)<<sqrt(solve());
fout.close();
}