Pagini recente » Cod sursa (job #405944) | Cod sursa (job #193698) | Cod sursa (job #2737084) | Rating Rares Ionescu (Rares.Ionescu) | Cod sursa (job #2073233)
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
void citire (int &n, vector <pair<int, int>> &PCT)
{
ifstream f("cmap.in");
f >> n;
for(int i = 0; i < n; i++)
{
int x, y;
f >> x >> y;
PCT.push_back (make_pair (x, y));
}
f.close();
}
long long distanta (pair<int, int> A, pair<int, int> B)
{
return (long long)(A.x - B.x) * (A.x - B.x) + (long long)(A.y - B.y) * (A.y - B.y);
}
bool cmp (pair<int, int> A, pair<int, int> B)
{
return A.y < B.y;
}
long long di (int st, int dr, vector <pair<int, int>> &PCT)
{
if(dr - st == 1)
{
return distanta (PCT[st], PCT[dr]);
///de inversat dupa daca este cazul, sa fie crescator dupa y
}
else if(dr - st == 2)
{
long long dist1 = distanta (PCT[st], PCT[st+1]);
long long dist2 = distanta (PCT[st], PCT[st+2]);
long long dist3 = distanta (PCT[st+1], PCT[st+2]);
long long minim = dist1;
if(dist2 < minim)
minim = dist2;
if(dist3 < minim)
minim = dist3;
return minim;
///interclasare
}
int m = (st + dr) / 2;
long long dist = min (di(st, m, PCT), di(m + 1, dr, PCT));
int delta = (int) (ceil(sqrt(dist)));
vector<pair<int,int>> temp;
for(unsigned i = st; i <= dr; i++)
if(abs(PCT[i].x - PCT[m].x) <= delta)
temp.push_back(PCT[i]);
sort(temp.begin(), temp.end(), cmp);
for(unsigned i = 0; i < temp.size(); i++)
for(unsigned j = i + 1; j <= i + 7 && j < temp.size(); j++)
dist = min(dist, distanta (temp[i], temp[j]));
return dist;
}
int main()
{
int n;
vector <pair<int, int>> PCT;
citire(n, PCT);
sort(PCT.begin(), PCT.end());
ofstream g("cmap.out");
g << fixed << setprecision(6) << sqrt(di(0, n - 1, PCT));
g.close();
return 0;
}