Pagini recente » Cod sursa (job #2642445) | Arhiva de probleme | Cod sursa (job #2270567) | Cod sursa (job #2773414) | Cod sursa (job #2521168)
#include <iostream>
#include <fstream>
#include <cmath>
#include <float.h>
#include <stdlib.h>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
struct punct
{
int x;
int y;
};
float distanta(punct a,punct b)
{
float d=sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
return d;
}
int compX(const void* a,const void* b)
{
punct *a1=(punct*)a;
punct *b1=(punct *)b;
return a1->x-b1->x;
}
int compY(const void* a,const void* b)
{
punct *a1=(punct*)a;
punct *b1=(punct *)b;
return a1->y-b1->y;
}
float minDistSubsir(punct v[],int leng,float dist)
{
float minDist=dist;
for(int i=0;i<leng;i++)
for(int j=i+1;j<leng&&(v[j].y-v[i].y)<minDist;j++)
if (distanta(v[i],v[j])<minDist)
minDist=distanta(v[i],v[j]);
return minDist;
}
float max3p(punct v[],int n)
{
float mini=FLT_MAX;
for (int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
if(distanta(v[i],v[j])<mini)
mini=distanta(v[i],v[j]);
return mini;
}
float min(float x, float y)
{
return (x < y)? x : y;
}
float minDist(punct vx[],punct vy[],int n)
{
if(n<=3)
return max3p(vx,n);
int m=n/2;
punct M=vx[m];
punct vys[m+1];
punct vyd[n-m-1];
int s=0,d=0;
for(int i=0;i<n;i++)
{
if (vy[i].x<=M.x)
vys[s++]=vy[i];
else
vyd[d++]=vy[i];
}
float ds=minDist(vx,vys,m);
float dd=minDist(vx+m,vyd,n-m);
float dist=min(ds,dd);
punct sir[n];
int j=0;
for (int i=0;i<n;i++)
if (abs(vy[i].x-M.x)<dist)
{
sir[j]=vy[i];
j++;
}
return min(dist,minDistSubsir(sir,j,dist));
}
int main()
{
int n;
fin>>n;
punct vx[n],vy[n];
for(int i=0;i<n;i++)
{
fin>>vx[i].x>>vx[i].y;
vy[i].x=vx[i].x;
vy[i].y=vx[i].y;
}
qsort(vx,n,sizeof(punct),compX);
qsort(vy,n,sizeof(punct),compY);
float d=minDist(vx,vy,n);
fout<<d;
return 0;
}