Pagini recente » Cod sursa (job #1880107) | Cod sursa (job #1479252) | Cod sursa (job #1840828) | Cod sursa (job #2827755) | Cod sursa (job #970660)
Cod sursa(job #970660)
#include <cmath>
#include <vector>
#include <cassert>
#include <fstream>
#include <iomanip>
#include <iterator>
#include <algorithm>
namespace std
{
inline istream& operator>>(istream& in, pair<int, int>& x)
{
in >> x.first >> x.second;
return in;
}
inline ostream& operator<<(ostream& out, const pair<int, int>& x)
{
out << '(' << x.first << ", " << x.second << ')';
return out;
}
}
using namespace std;
typedef long long int lld;
typedef pair<int, int> point;
vector<point> Px, Py, aux;
inline lld dist(const point& x, const point& y)
{
return 1LL * (x.first - y.first) * (x.first - y.first) +
1LL * (x.second - y.second) * (x.second - y.second);
}
inline lld abs(lld x) {return x <= 0 ? -x : x;}
inline bool cmpY(const point& x, const point& y)
{
return (x.second < y.second) || (x.second == y.second && x.first < y.first);
}
inline lld closestPair(vector<point>& P, int left, int right)
{
if(left >= right) return -1;
if(right - left <= 9)
{
int i, j;
lld minim = dist(P[left], P[right]);
for(i = left; i < right; ++i)
{
for(j = i + 1; j <= right; ++j)
{
minim = min(minim, dist(P[i], P[j]));
if(!cmpY(P[i], P[j]))
{
swap(P[i], P[j]);
}
}
}
return minim;
}
lld minim;
int middle = (left + right) >> 1, i, j, k;
minim = min(closestPair(P, left, middle), closestPair(P, middle + 1, right));
merge(P.begin() + left, P.begin() + middle + 1,
P.begin() + middle + 1, P.begin() + right + 1,
aux.begin() + left, cmpY);
copy(aux.begin() + left, aux.begin() + right + 1, P.begin() + left);
for(i = j = left; i <= right; ++i)
{
if(abs(P[i].first - Px[middle].first) < minim)
{
aux[j++] = P[i];
}
}
for(i = left; i < j; ++i)
{
for(k = 1; k <= 7 && i + k < j; ++k)
{
minim = min(minim, dist(aux[i], aux[i + k]));
}
}
return minim;
}
int main()
{
int N;
ifstream in("cmap.in");
ofstream out("cmap.out");
in >> N;
copy(istream_iterator<point>(in), istream_iterator<point>(), back_inserter(Px));
sort(Px.begin(), Px.end());
Py = Px;
aux.resize(Py.size());
out << setprecision(6) << fixed << sqrt(closestPair(Py, 0, Py.size() - 1)) << '\n';
return EXIT_SUCCESS;
}