Pagini recente » Cod sursa (job #1880405) | Cod sursa (job #901871) | Cod sursa (job #1692247) | Cod sursa (job #1390191) | Cod sursa (job #1047101)
#include <iostream>
#include <fstream>
#include <math.h>
#include <stdlib.h>
#include <algorithm>
std::ifstream fin("cmap.in");
std::ofstream fout("cmap.out");
struct vertex
{
long long x, y;
};
vertex vec1[100001], vec2[100001];
inline bool cmp(vertex a, vertex b)
{
if(a.x < b.x)
{
return true;
}
else
if(a.x == b.x)
{
if(a.y < b.y)
{
return true;
}
}
return false;
}
double distance(vertex a, vertex b)
{
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
void citire(int &n, vertex noduri[])
{
fin>>n;
for(int i = 0; i < n; i++)
{
fin>>noduri[i].x>>noduri[i].y;
}
}
void intercls(int in, int m, int sf)
{
int i = in, j = m + 1, k = 0;
while (i <= m && j <= sf)
{
if (vec1[i].y < vec1[j].y)
{
vec2[k] = vec1[i];
i++;
}
else
{
vec2[k] = vec1[j];
j++;
}
k++;
}
while (i <= m)
{
vec2[k] = vec1[i];
k++;
i++;
}
while (j <= sf)
{
vec2[k] = vec1[j];
k++;
j++;
}
for (int i = in; i<= sf; i++)
{
vec1[i] = vec2[i - in];
}
}
double rezolvare2(int in, int sf)
{
if (sf == in)
{
return 1000000001;
}
if (sf - in == 1)
{
return distance(vec1[in], vec1[sf]);//, vec2[sf]);
}
int m = (in + sf) / 2;
double stVal = rezolvare2(in, m);
double drVal = rezolvare2(m + 1, sf);
double minDist = 0;
if(stVal > drVal)
{
minDist = drVal;
}
else
{
minDist = stVal;
}
int some = vec1[m].x;
intercls(in, m, sf);
int k = 0;
for (int i = in; i <= sf; i++)
{
if (abs(some - vec1[i].x) <= minDist)
{
vec2[k] = vec1[i];
k++;
}
}
double newMin = 10000000001;
for (int i = 0; i < k; i++)
{
int j = i + 1;
while(j < k && j < i + 8)
{
newMin = distance(vec2[i], vec2[j]);
if(newMin < minDist)
{
minDist = newMin;
}
j++;
}
}
return minDist;
}
int main()
{
int n;
//vertex noduri[100001];
citire(n, vec1);
std::sort(vec1, vec1 + n, cmp);
double minimum = rezolvare2(0, n - 1);
fout<<minimum<<'\n';
return 0;
}