Pagini recente » Cod sursa (job #2276845) | Cod sursa (job #1063584) | Cod sursa (job #305551) | Cod sursa (job #1287973) | Cod sursa (job #2065020)
#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
struct punct
{
double x, y;
};
vector<punct> v, A;
unsigned int n;
double dist(punct A, punct B)
{
return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}
bool cmp(const punct A, const punct B)
{
if(A.x < B.x)
{
return 1;
}
else if(A.x == B.x and A.y < B.y)
{
return 1;
}
return 0;
}
bool cmp2(const punct A, const punct B)
{
if(A.y < B.y)
{
return 1;
}
else if(A.y == B.y and A.x < B.x)
{
return 1;
}
return 0;
}
void citire()
{
fin >> n;
v.resize(n);
A.resize(n);
for(int i = 0; i < n; ++i)
{
fin >> v[i].x >> v[i].y;
}
}
double divide(unsigned int st, unsigned int dr)
{
if(st == dr)
{
return 9999999;
}
else
{
unsigned int mid = (st + dr) / 2, st1, dr1;
double dist1, dist2, d, midX, midY, minim;
dist1 = divide(st, mid);
dist2 = divide(mid + 1, dr);
d = min(dist1, dist2);
double e = d;
midX = v[mid].x;
st1 = mid;
while(abs(v[st1].x - midX) <= d and st1 >= st)
{
--st1;
}
++st1;
dr1 = mid;
while(abs(v[dr1].x - midX) <= d and dr1 < dr)
{
--dr1;
}
++dr1;
for(int i = st; i <= dr; ++i)
{
A[i] = v[i];
}
sort(A.begin() + st, A.begin() + mid, cmp2);
sort(A.begin() + mid + 1, A.begin() + dr, cmp2);
for(int i = st; i <= mid; ++i)
{
for(int j = mid + 1; j <= dr; ++j)
{
if(e > dist(A[i], A[j]))
{
e = dist(A[i],A[j]);
}
else
{
break;
}
}
}
return e;
}
}
int main()
{
citire();
sort(v.begin(), v.end(), cmp);
fout.precision(15);
fout << divide(0, n - 1);
}