Pagini recente » Cod sursa (job #2233097) | Cod sursa (job #466954) | Cod sursa (job #1836093) | Cod sursa (job #1804919) | Cod sursa (job #767304)
Cod sursa(job #767304)
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <limits>
#include <math.h>
#define NMAX 100001
using namespace std;
typedef struct Point {
int x;
int y;
} Point;
Point P[NMAX];
int N;
Point make_point(int X, int Y) {
Point pct;
pct.x = X;
pct.y = Y;
return pct;
}
void read_() {
scanf("%d", &N);
for (int i = 0; i < N; i++) {
int X, Y;
scanf("%d%d", &X, &Y);
P[i] = make_point(X,Y);
}
}
int myComp(const void * a, const void * b) {
int X1, X2;
X1 = (*(Point*)a).x;
X2 = (*(Point*)b).x;
if (X1 != X2) {
return (X1 - X2);
} else {
int Y1, Y2;
Y1 = (*(Point*)a).y;
Y2 = (*(Point*)b).y;
return (Y1 - Y2);
}
}
float D(Point a, Point b) {
return (sqrt((float)pow((a.x - b.x), 2) + (float)pow((a.y - b.y), 2)));
}
float calc_dist_max3(int p1, int p2) {
float min = (float)numeric_limits<float>::max();
for (int i = p1; i < p2; i++) {
for (int j = i + 1; j <= p2; j++) {
float d = D(P[i], P[j]);
if (d < min) {
min = d;
}
}
}
return min;
}
float min_(float d1, float d2) {
return (d1 < d2 ? d1 : d2);
}
float solve_mid(float d, vector<Point> vs, vector<Point> vd) {
vector<Point>::iterator itS, itD;
for (itS = vs.begin(); itS != vs.end(); itS++) {
Point ps = *itS;
for (itD = vd.begin(); itD != vd.end(); itD++) {
Point pd = *itD;
if ((pd.x - ps.x) >= d) {
break;
}
if (abs(ps.y - pd.y) < d) {
d = min_(d, D(ps, pd));
}
}
}
return d;
}
float solve(int p1, int p2) {
if (p2 - p1 <= 2) {
return calc_dist_max3(p1, p2);
}
else {
int mid = (p1 + p2) / 2;
float d = min_(solve(p1, mid), solve(mid + 1, p2));
vector<Point> vs;
vector<Point> vd;
int val = P[mid].x;
int i = mid;
while ((val - P[i].x) < d) {
vs.push_back(P[i]);
i--;
}
i = mid + 1;
while ((P[i].x - val) < d) {
vd.push_back(P[i]);
i++;
}
d = solve_mid(d, vs, vd);
return d;
}
}
void print_vec() {
for (int i = 0; i < N; i++) {
printf("(%d, %d); ",P[i].x, P[i].y);
}
}
int main() {
freopen("cmap.in", "r", stdin);
freopen("cmap.out", "w", stdout);
read_();
qsort(P, N, sizeof(Point), myComp);
float d = solve(0, N-1);
printf("%f", d);
//print_vec();
return 0;
}