Pagini recente » Cod sursa (job #985361) | Cod sursa (job #2930677) | Cod sursa (job #871308) | Cod sursa (job #2251038) | Cod sursa (job #3273333)
//#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <utility>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
//ifstream fin("input.txt");
//ofstream fout("output.txt");
typedef pair<int, int> Pont; // .first = x, .second = y
long long dist2(Pont p1, Pont p2)
{
long long dx = p1.first - p2.first;
long long dy = p1.second - p2.second;
return dx*dx + dy*dy;
}
inline bool ycomp(Pont p1, Pont p2)
{
return p1.second < p2.second
|| (p1.second == p2.second && p1.first < p2.first);
}
void osszefesul(
vector<Pont> &ty, int bal, int kozep, int jobb, vector<Pont> &temp)
{
// temp[bal]...temp[jobb]
int itemp = bal;
int ib = bal;
int ij = kozep+1;
while (ib <= kozep || ij <= jobb) {
if (ib <= kozep && (ij > jobb || ycomp(ty[ib], ty[ij]))) {
temp[itemp] = ty[ib];
itemp++;
ib++;
}
else {
temp[itemp] = ty[ij];
itemp++;
ij++;
}
}
for (int i = bal; i <= jobb; i++)
ty[i] = temp[i];
}
inline void rendezy(vector<Pont> &t, int bal, int jobb)
{
for (int i = bal+1; i <= jobb; i++) {
Pont temp = t[i];
int j = i;
while (j > bal && ycomp(temp, t[j-1])) {
t[j] = t[j-1];
j--;
}
t[j] = temp;
}
}
long long megold(int bal, int jobb, vector<Pont> &t, vector<Pont> &ty)
{
if (jobb-bal+1 <= 3) {
for (int i = bal; i <= jobb; i++)
ty[i] = t[i];
rendezy(ty, bal, jobb);
long long dmin = dist2(t[bal], t[bal+1]);
for (int i = bal; i <= jobb; i++)
for (int j = i+1; j <= jobb; j++) {
long long d = dist2(t[i], t[j]);
if (d < dmin)
dmin = d;
}
return dmin;
}
else {
int kozep = (bal+jobb) / 2;
int xkozep = t[kozep].first;
long long dmin_bal = megold(bal, kozep, t, ty);
long long dmin_jobb = megold(kozep+1, jobb, t, ty);
long long dmin = min(dmin_bal, dmin_jobb);
osszefesul(ty, bal, kozep, jobb, t);
Pont buf[7];
int nbuf = min(7, jobb-bal+1);
int ibuf = 0;
for (int i = bal; i <= jobb; i++)
if (abs(t[i].first - xkozep) <= dmin) {
for (int j = 0; j < ibuf; j++) {
long long d = dist2(ty[i], buf[j]);
if (d < dmin)
dmin = d;
if (ibuf == nbuf && j > 0)
buf[j-1] = buf[j];
}
if (ibuf < nbuf) {
buf[ibuf] = ty[i];
ibuf++;
}
else {
buf[nbuf-1] = ty[i];
}
}
return dmin;
}
}
int main()
{
int n;
fin >> n;
vector<Pont> t(n);
for (int i = 0; i < n; i++)
fin >> t[i].first >> t[i].second;
vector<Pont> ty(n);
sort(t.begin(), t.end());
fout << fixed << setprecision(7) << sqrt(megold(0, n-1, t, ty)) << endl;
return 0;
}