Pagini recente » Cod sursa (job #2555063) | Cod sursa (job #1889877) | Cod sursa (job #1100752) | Cod sursa (job #1830134) | Cod sursa (job #2089083)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#define X first
#define Y second
#define Punct pair <long long, long long>
using namespace std;
ifstream in("cmap.in");
ofstream out("cmap.out");
Punct PointX[100010], PointY[100010];
Punct Distante[100010];
int n;
bool dupaX(Punct a, Punct b)
{
if(a.X == b.X)
return a.Y < b.Y;
return a.X < b.X;
}
bool dupaY(Punct a, Punct b)
{
if(a.Y == b.Y)
return a.X < b.X;
return a.Y < b.Y;
}
void citire()
{
in >> n;
for(int i = 0; i < n; i++)
{
in >> PointX[i].X >> PointX[i].Y;
PointY[i].X = PointX[i].X;
PointY[i].Y = PointX[i].Y;
}
sort(PointX, PointX + n, dupaX);
sort(PointY, PointY + n, dupaY);
// for(int i = 0; i < n; i++)
// cout << PointX[i].X << " " << PointX[i].Y << "\n";
// cout << endl;
// for(int i = 0; i < n; i++)
// cout << PointY[i].X << " " << PointY[i].Y << "\n";
// cout << endl;
}
long long dist(Punct a, Punct b)
{
long long difX = (a.X - b.X);
long long difY = (a.Y - b.Y);
return difX * difX + difY * difY;
}
long long divide(int st, int dr, Punct vec[], int len)
{
if(dr - st == 1)
return dist(PointX[st], PointX[dr]);
if(dr - st == 2)
return min(dist(PointX[st], PointX[st + 1]), min(dist(PointX[st+1], PointX[dr]), dist(PointX[st], PointX[dr])));
int m = (st + dr) / 2;
int counterL = 0;
int counterR = 0;
Punct Left[len + 10];
Punct Right[len + 10];
for(int i = 0; i < len; i++)
{
if(vec[i].X < PointX[i].X)
{
Left[counterL].X = vec[i].X;
Left[counterL].Y = vec[i].Y;
counterL++;
}
else
{
Right[counterR].X = vec[i].X;
Right[counterR].Y = vec[i].Y;
counterR++;
}
}
long long S1 = divide(st, m, Left, counterL - 1);
long long S2 = divide(m + 1, dr, Right, counterR - 1);
long long d = min(S1, S2);
int k = 0;
long long delta = ceil(sqrt(d));
for(int i = 0; i <= len; i++)
{
if( abs( vec[i].X - PointX[m].X ) <= delta )
{
Distante[k].X = vec[i].X;
Distante[k].Y = vec[i].Y;
k++;
}
}
for(int i = 0; i < k; i++)
{
for(int j = i + 1; j <= (i+7) && j < k; j++)
d = min(d, dist(Distante[i], Distante[j]));
}
return d;
}
int main()
{
citire();
out << sqrt(divide(0, n - 1, PointY, n - 1));
return 0;
}