Pagini recente » Cod sursa (job #1164343) | Cod sursa (job #1585357) | Cod sursa (job #1357691) | Monitorul de evaluare | Cod sursa (job #3357810)
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
#include <time.h>
#include <iomanip>
#include <deque>
#include <math.h>
#include <cmath>
#include <assert.h>
#include <stack>
#include <bitset>
#include <random>
#include <chrono>
using namespace std;
const double PI = acos(-1);
const double eps = 1e-6;
inline long long lgput(long long a , long long b , long long mod) {
long long ret = 1;
while( b ){
if(b & 1) ret = (ret * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return (ret%mod);
}
inline long long inv(long long x , long long MOD) {
return lgput(x, MOD - 2, MOD);
}
inline bool exist (double nr){
return (nr < -eps) || (nr > eps);
}
long long big_rand(){
return rand () * RAND_MAX + rand();
}
//-----------------------------------------------------------------
#include <fstream>
ifstream cin ("cmap.in"); ofstream cout ("cmap.out");
struct nod {
int x, y;
};
bool cmpx(nod a, nod b) { return a.x < b.x; }
bool cmpy(nod a, nod b) { return a.y < b.y; }
nod v[100100], ord[100100];
double dist(nod a, nod b) {
return sqrt(1LL * (a.x - b.x) * (a.x - b.x) + 1LL * (a.y - b.y) * (a.y - b.y));
}
double solve(int st, int dr) {
double ans = 1e18;
if (dr - st + 1 <= 3) {
for (int i = st; i <= dr; i++) {
for (int j = i + 1; j <= dr; j++) {
ans = min(ans, dist(v[i], v[j]));
}
}
sort(v + st, v + dr + 1, cmpy);
return ans;
}
int mij = (st + dr) / 2;
int middle = v[mij].x;
double low = min(solve(st, mij), solve(mij + 1, dr));
int ST = st, DR = mij + 1, pnt = st;
while (ST <= mij && DR <= dr) {
if (v[ST].y < v[DR].y) {
ord[pnt++] = v[ST++];
} else {
ord[pnt++] = v[DR++];
}
}
while (ST <= mij) ord[pnt++] = v[ST++];
while (DR <= dr) ord[pnt++] = v[DR++];
for (int i = st; i <= dr; i++) {
v[i] = ord[i];
}
vector<nod> strip;
for (int i = st; i <= dr; i++) {
if (abs(v[i].x - middle) <= low) {
strip.push_back(v[i]);
}
}
ans = low;
for (int i = 0; i < (int)strip.size(); i++) {
for (int j = i + 1; j < (int)strip.size() && (strip[j].y - strip[i].y) < ans; j++) {
ans = min(ans, dist(strip[i], strip[j]));
}
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cout << setprecision(6) << fixed;
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> v[i].x >> v[i].y;
}
sort(v + 1, v + n + 1, cmpx);
cout << solve(1, n);
return 0;
}