Pagini recente » Cod sursa (job #1164145) | Cod sursa (job #605624) | Cod sursa (job #2255503) | Cod sursa (job #1058779) | Cod sursa (job #2070925)
#include <iostream>
#include <stdlib.h>
#include <math.h>
#include <fstream>
#include <climits>
using namespace std;
struct point
{
int x, y;
};
struct cuplu
{
point unu, doi;
};
cuplu a,b;
point pct1, pct2, aux1, aux2;
int compx(const void* a, const void* b)
{
point *p1 = (point *)a;
point *p2 = (point *)b;
return (p1->x - p2->x);
}
int compy(const void* a, const void* b)
{
point *p3 = (point *)a;
point *p4 = (point *)b;
return (p3->y - p4->y);
}
//calculul distantei
float dist(point a, point b)
{
return sqrt((a.x - b.x)*(a.x - b.x)+(a.y - b.y)*(a.y - b.y));
}
float verif(point s[], int dim, float d)
{
float min=d;
for(int i=0;i<dim-1;i++)
for(int j=i+1;j<dim&&(s[j].y-s[i].y)<min;j++)
if (dist(s[i],s[j])<min)
{
min=dist(s[i],s[j]);
if(s[i].x!=aux1.x&&s[i].y!=aux1.y&&s[j].x!=aux2.x&&s[j].y!=aux2.y)
{ aux1=s[i];
aux2=s[j];
b.unu=aux1;
b.doi=aux2;
}
}
return min;
}
float mn=INT_MAX;
float dei(point X[], point Y[], int n)
{
if(n<=3)
{
int i, j;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if(dist(X[i],X[j])<mn)
{
mn=dist(X[i],X[j]);
pct1=X[i];
pct2=X[j];
a.unu=pct1;
a.doi=pct2;
}
return mn;
}
int mid=n/2;
point midp=X[mid];
point pyleft[mid+1];
point pyright[n-mid-1];
int l=0,r=0;
for(int i=0;i<n;i++)
{
if (Y[i].x<=midp.x)
pyleft[l++]=Y[i];
else
pyright[r++]=Y[i];
}
float left=dei(X,pyleft,mid);
float right=dei(X+mid,pyright,n-mid);
float minim=min(left,right);
point closest[n];
int j=0;
for(int i=0;i<n;i++)
if(abs(Y[i].x-midp.x)<minim)
{
closest[j]=Y[i];
j++;
}
if(minim<verif(closest, j, minim))
{
pct1=a.unu;
pct2=a.doi;
}
else if(verif(closest, j, minim)<minim)
{
pct1=b.unu;
pct2=b.doi;
}
return min(minim, verif(closest, j, minim));
}
int main()
{
int n;
ifstream f("cmap.in");
ofstream g("cmap.out");
f>>n;
point puncte[n];
for(int i=0;i<n;i++)
{
point a;
f>>a.x>>a.y;
puncte[i]=a;
}
aux1.x=aux1.y=aux2.x=aux2.y=INT_MAX;
a.unu.x=a.unu.y=a.doi.x=a.doi.y=b.unu.x=b.unu.y=b.doi.x=b.doi.y=INT_MAX;
point X[n];
point Y[n];
for(int i=0;i<n;i++)
{
X[i]=puncte[i];
Y[i]=puncte[i];
}
qsort(X, n, sizeof(point), compx);
qsort(Y, n, sizeof(point), compy);
//for(int i=0;i<n;i++)
// cout<<X[i].x<<" ";
float distanta=dei(X,Y,n);
g<<"Distanta este "<<distanta<<" intre punctele ("<<pct1.x<<" "<<pct1.y<<") si ("<<pct2.x<<" "<<pct2.y<<").";
return 0;
}