Pagini recente » Cod sursa (job #27836) | Cod sursa (job #3273934) | Cod sursa (job #1513851) | Cod sursa (job #2971698) | Cod sursa (job #2971898)
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <bits/stdc++.h>
using namespace std;
#define NMAX 100001
#define INF 1.7976931348623158e+308
struct pct {
int x, y;
};
int n;
pct p[NMAX];
int nv;
pct pv[NMAX];
inline bool cmpx(const pct& p1, const pct& p2) {
return p1.x==p2.x ? p1.y<p2.y : p1.x<p2.x;
}
inline bool cmpy(const pct& p1, const pct& p2) {
return p1.y==p2.y ? p1.x<p2.x : p1.y<p2.y;
}
inline double dist(const pct& p1, const pct& p2) {
return sqrt(((long long int)p1.x - p2.x) * (p1.x - p2.x) + ((long long int)p1.y - p2.y) * (p1.y - p2.y));
}
double finddistmin(int st, int dr) {
double distmin;
int i, j;
distmin = INF;
for (i=st; i<dr; i++) {
for (j=i+1; j<=dr; j++) {
distmin = min(distmin, dist(p[i], p[j]));
}
}
return distmin;
}
double verif(double distmin) {
int i, j;
sort(pv, pv+nv, cmpy);
for (i=0; i<nv-1; i++) {
j = i+1;
while (j<nv && pv[j].y-pv[i].y<distmin) {
distmin = min(distmin, dist(pv[i], pv[j]));
j++;
}
}
return distmin;
}
double cmap(int st, int dr) {
int mijl;
double distmin;
if (dr-st+1 <= 3) {
return finddistmin(st, dr);
}
mijl = (dr+st)/2;
distmin = min(cmap(st, mijl), cmap(mijl+1, dr));
nv = 0;
for (; st<=dr; st++) {
if (abs(p[st].x-p[mijl].x) < distmin) {
pv[nv] = p[st];
nv++;
}
}
return min(distmin, verif(distmin));
}
int main() {
FILE *fin, *fout;
fin = fopen("cmap.in", "r");
fout = fopen("cmap.out", "w");
int n, i;
double rez;
fscanf(fin, "%d", &n);
for (i=0; i<n; i++) {
fscanf(fin, "%d%d", &p[i].x, &p[i].y);
}
sort(p, p+n, cmpx);
rez = cmap(0, n-1);
fprintf(fout, "%lf\n", rez);
fclose(fin);
fclose(fout);
return 0;
}