Pagini recente » Cod sursa (job #330072) | Cod sursa (job #3135624) | Cod sursa (job #2461122) | Cod sursa (job #951826) | Cod sursa (job #2731826)
#include<iostream>
#include<fstream>
#include<math.h>
#include<algorithm>
#include<iomanip>
using namespace std;
ifstream fin ("cmap.in");
ofstream fout ("cmap.out");
struct punct
{
int x, y;
};
double distanta(punct p1, punct p2)
{
return sqrt( (p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y));
}
void mergesortX(punct v[], int st, int dr)
{
if(st == dr)
return;
int mid = (st + dr) / 2;
mergesortX(v, st, mid);
mergesortX(v, mid+1, dr);
struct punct t[dr-st+1];
int k=0;
int i=st, j=mid+1;
while(i<=mid && j<=dr)
{
if(v[i].x < v[j].x)
{
t[k++]=v[i++];
}
else
{
t[k++]=v[j++];
}
}
while(i<=mid)
{
t[k++]=v[i++];
}
while(j<=dr)
{
t[k++]=v[j++];
}
for(int p=st; p<=dr; p++)
{
v[p]=t[p-st];
}
}
void mergesortY(punct v[], int st, int dr)
{
if(st == dr)
return;
int mid = (st + dr) / 2;
mergesortY(v, st, mid);
mergesortY(v, mid+1, dr);
struct punct t[dr-st+1];
int k=0;
int i=st, j=mid+1;
while(i<=mid && j<=dr)
{
if(v[i].y < v[j].y)
{
t[k++]=v[i++];
}
else
{
t[k++]=v[j++];
}
}
while(i<=mid)
{
t[k++]=v[i++];
}
while(j<=dr)
{
t[k++]=v[j++];
}
for(int p=st; p<=dr; p++)
{
v[p]=t[p-st];
}
}
double sol1(punct v[], int n) //pentru 2 sau 3 puncte
{
double dmin = 100000;
for(int i = 0; i < n; i++)
for(int j = i + 1; j < n; j++)
if(distanta(v[i], v[j]) < dmin)
dmin = distanta(v[i], v[j]);
return dmin;
}
double cmap(punct vx[], punct vy[], int n)
{
if(n <= 3)
return sol1(vx, n);
int mij = n / 2;
punct pst[mij];
punct psd[n - mij];
int st = 0, dr = 0;
for(int i = 0; i < n; i++)
{
if(vy[i].x <= vx[mij].x)
pst[st++] = vy[i];
else
psd[dr++] = vy[i];
}
double left = cmap(vx, pst, mij);
double right = cmap(vx + mij, psd, n - mij);
double d = min(left, right);
punct utile[n];
int m = 0;
for(int i = 0; i < n; i++)
if(abs(vy[i].x - vx[mij].x) < d)
{
utile[m] = vy[i];
m++;
}
for(int i = 0; i < m; i++)
for(int j = i + 1; j < m && j < i + 8; j++)
if(distanta(utile[i], utile[j]) < d)
d = distanta(utile[i], utile[j]);
return d;
}
int main()
{
punct vx[100000];
punct vy[100000];
int n;
fin >> n;
for(int i = 0; i < n; i++)
fin >> vx[i].x >> vx[i].y;
for(int i = 0; i < n; i++)
vy[i] = vx[i];
mergesortX(vx, 0, n - 1);
mergesortY(vy, 0, n - 1);
fout << fixed << setprecision(8);
fout << cmap(vx, vy, n);
return 0;
}