Pagini recente » Cod sursa (job #3003840) | Cod sursa (job #2945339) | Cod sursa (job #1130091) | Cod sursa (job #39324) | Cod sursa (job #1618117)
#include <fstream>
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <math.h>
#include<iomanip>
struct Point{
int x, y;
};
#define INF 0x7fffffff
bool cmp_x(Point p1, Point p2){
return p1.x < p2.x;
}
bool cmp_y(Point p1, Point p2){
return p1.y < p2.y;
}
double dist(const Point& p1, const Point& p2){
return sqrt(pow((double)(p1.x - p2.x), 2) + pow((double)(p1.y - p2.y), 2));
}
std::vector<Point>slice(std::vector<Point> v, int start, int end){
std::vector<Point> a;
a.assign(v.begin() + start, v.begin() + end);
return a;
}
double brute_force(std::vector<Point> v){
double dmin = INF;
for(size_t i = 0; i < v.size() - 1; i++)
for(size_t j = i+1; j < v.size(); j++)
dmin = std::min(dmin, dist(v[i], v[j]));
return dmin;
}
double split_plane(std::vector<Point>v){
if(v.size()<=3){
return brute_force(v);
}else{
int lm = v.size() / 2;
int xm = v[lm].x; /*dreapta care imparte planul*/
double dmin = std::min(split_plane(slice(v, 0, lm+1)), split_plane(slice(v, lm+1, v.size())));
int li, ls;
for(li = lm; li >= 1 && abs(v[li].x - xm) < dmin; li--);
for(ls = lm; ls < v.size() && abs(v[ls].x - xm) < dmin; ls++);
std::vector<Point> region; /*vector de puncte delimitat de distana d*/
region = slice(v, li, ls);
std::sort(region.begin(), region.end(), cmp_y);
for(size_t i = 0; i < region.size(); i++)
for(size_t j = 1; j < 8; j++)
if(i + j < region.size())
dmin = std::min(dmin, dist(region[i], region[i+j]));
return dmin;
}
}
int main(){
std::ifstream fin("cmap.in");
std::ofstream fout("cmap.out");
std::vector<Point> v;
Point p;
int n;
fin >> n;
for(int i = 0; i < n; i++){
fin >> p.x >> p.y;
v.push_back(p);
}
std::sort(v.begin(), v.end(), cmp_x);
fout << std::setprecision(6) << std::fixed<< split_plane(v) << '\n';
return 0;
}