Pagini recente » Cod sursa (job #1292961) | Cod sursa (job #252837) | Cod sursa (job #2864848) | Cod sursa (job #2565119) | Cod sursa (job #1617032)
#include <fstream>
#include <iostream>
#include <stdlib.h>
#include <vector>
#include <math.h>
struct Point{
int x, y;
};
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;
}
/*
std::ostream& operator << (std::ostream& out, Point p){
out << "("<< p.x << "," << p.y << ")";
return out;
}*/
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 brute_force(Point *v, int li, int ls){
double minim = dist(v[li], v[ls]); //initializez minimul;
for(int i = li; i < ls; i++){
for(int j = i+1; j <= ls; j++){
if(li != ls){
double d = dist(v[i], v[j]);
if(d < minim) minim = d;
}
}
}
return minim;
}
double split_plane(Point *v, int li, int ls){
if(ls - li <= 3)
return brute_force(v, li, ls);
else{
int lm = (li + ls) / 2;
int xm = v[lm].x; /*dreapta care imparte planul*/
double dmin1 = split_plane(v, li, lm);
double dmin2 = split_plane(v, lm+1, ls);
double dmin = std::min(dmin1, dmin2);
std::vector<Point> region; /*vector de puncte delimitat de distana d*/
for(int i = li; i <= ls; i++)
if(abs(xm - v[i].x) < dmin)
region.push_back(v[i]);
for(size_t i = 0; i < region.size() - 1; i++){
for(size_t k = i+1; k < region.size() && abs(v[i].y - v[k].y) < dmin; k++)
if(abs(v[i].y - v[k].y) < dmin)
dmin = abs(v[i].y - v[k].y);
}
return dmin;
}
}
int main(){
std::ifstream fin("cmap.in");
std::ofstream fout("cmap.out");
int n;
fin >> n;
Point v[n];
for(int i = 0; i < n; i++){
fin >> v[i].x >> v[i].y;
}
qsort(v, n, sizeof(Point), compare);
/*
for(int i = 0; i < n; i++)
std::cout << v[i] << std::endl;
*/
double dmin = split_plane(v, 0, n-1);
fout.precision(8);
fout << dmin << '\n';
fin.close();
fout.close();
return 0;
}