Pagini recente » Cod sursa (job #2731746) | Cod sursa (job #1625630) | Cod sursa (job #23197) | Cod sursa (job #3213096) | Cod sursa (job #1617731)
#include <fstream>
#include <iostream>
#include <stdlib.h>
#include <vector>
#include <math.h>
struct Point{
int x, y;
};
#define INF 0x7fffffff
int compare(const void *a, const void *b){
Point *p1 = (Point*) a;
Point *p2 = (Point*) b;
if(p1->x > p2->x) return 1;
else if(p1->x == p2->x){
if(p1->y > p2->y) return 1;
else if(p1->y == p2->y) return 0;
else return 0;
}else return -1;
}
double dist(const Point& p1, const Point& p2){
return sqrt(pow((double)(p1.x - p2.x), 2) + pow((double)(p1.y - p2.y), 2));
}
double split_plane(Point *v, int li, int ls){
if(ls - li<=2){
double dmin1 = std::min(dist(v[li], v[li+1]), dist(v[li+1], v[li+2]));
return std::min(dmin1, dist(v[li], v[li+2]));
}else{
int lm = (li + ls) / 2;
int xm = v[lm].x; /*dreapta care imparte planul*/
double dmin = std::min(split_plane(v, li, lm), split_plane(v, lm+1, ls));
std::vector<Point> region; /*vector de puncte delimitat de distana d*/
for(int i = lm; i >=li && abs(xm - v[i].x) < dmin; i--)
for(int j = 1; j <= 6 && (i+j <= ls); j++)
dmin = std::min(dmin, dist(v[i], v[i+j]));
return dmin;
}
}
int main(){
std::ifstream fin("cmap.in");
std::ofstream fout("cmap.out");
int n;
fin >> n;
Point v[n+1];
for(int i = 0; i < n; i++){
fin >> v[i].x >> v[i].y;
}
qsort(v, n, sizeof(Point), compare);
double dmin = split_plane(v, 0, n-1);
fout.precision(8);
fout << dmin << '\n';
fin.close();
fout.close();
return 0;
}