Pagini recente » Cod sursa (job #1904652) | Cod sursa (job #2030478) | Cod sursa (job #2014494) | Cod sursa (job #374850) | Cod sursa (job #3307161)
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <iomanip>
using namespace std;
const int NMAX = 100000;
using ll = long long;
ifstream cin("cmap.in");
ofstream cout("cmap.out");
struct puncte {
ll x, y;
bool operator <(const puncte & rhs) const {
if(x != rhs.x)
return x < rhs.x;
return y < rhs.y;
}
}v[NMAX + 2], ord[NMAX + 2];
long double ans = 2e9 * sqrt(2);
long double dist(puncte a, puncte b) {
return 1LL * sqrt(1LL * (a.x - b.x) * (a.x - b.x) + 1LL * (a.y - b.y) * (a.y - b.y));
}
void divide(int st, int dr) {
if(st + 1 >= dr) {
if(st + 1 == dr) {
///MERGESORT
if(ord[st].y > ord[dr].y || (ord[st].y == ord[dr].y && ord[st].x > ord[dr].x))
swap(ord[st], ord[dr]);
ans = min(ans, dist(v[st], v[dr]));
}
return;
}
int mid = (st + dr) / 2;
divide(st, mid);
divide(mid + 1, dr);
vector <puncte> nou; ///MERGESORT
int pos1 = st, pos2 = mid + 1;
while(pos1 <= mid && pos2 <= dr) {
if(ord[pos1].y < ord[pos2].y || (ord[pos1].y == ord[pos2].y && ord[pos1].x < ord[pos2].x)) {
nou.push_back(ord[pos1]);
pos1++;
}
else {
nou.push_back(ord[pos2]);
pos2++;
}
}
while(pos1 <= mid) {
nou.push_back(ord[pos1]);
pos1++;
}
while(pos2 <= dr) {
nou.push_back(ord[pos2]);
pos2++;
}
for(int i = st; i <= dr; i++) {
ord[i].x = nou[i - st].x;
ord[i].y = nou[i - st].y;
}
///INAPOI LA CE PUNCTE AVEM NEVOIE
nou.clear();
int lin = v[mid].x; ///ca eu acolo am impartit
for(int i = st; i <= dr; i++) {
if((ord[i].x <= lin && ord[i].x + ans <= lin) ||
(ord[i].x > lin && ord[i].x - ans <= lin))
nou.push_back(ord[i]);
}
long double d = ans;
for(int i = 0; i < nou.size(); i++) {
for(int j = i + 1; j < min((int)nou.size(), i + 8); j++) { ///doar urm 7
d = min(d, dist(nou[i], nou[j]));
}
}
ans = min(ans, d);
}
int main() {
int n;
cin >> n;
for(int i = 1; i <= n; i++)
cin >> v[i].x >> v[i].y;
sort(v + 1, v + n + 1);
for(int i = 1; i <= n; i++) { ///merge sort pt y
ord[i].x = v[i].x;
ord[i].y = v[i].y;
}
divide(1, n);
cout << setprecision(6) << fixed << ans;
return 0;
}