Pagini recente » Cod sursa (job #2693683) | Cod sursa (job #78024) | Cod sursa (job #2926280) | Cod sursa (job #854274) | Cod sursa (job #1617480)
#include <fstream>
#include <vector>
#include <math.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#define INF 0x7fffff
struct Point{
int x, y;
};
int x_cmp(Point p1, Point p2){
return p1.x < p2.x;
}
bool y_cmp(Point p1, Point p2){
return p1.y < p2.y;
}
/*
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(std::vector<Point> v){
double minim = INF; //initializez minimul;
for(size_t i = 0; i < v.size()-1; i++){
for(int j = i+1; j <= v.size(); j++){
if(i != j){
double d = dist(v[i], v[j]);
if(d < minim) minim = d;
}
}
}
return minim;
}
double split_plane(std::vector<Point> v){
if(v.size()<= 3){
return brute_force(v);
}else{
int lm = (int)(v.size()/2);
int xm = v[lm].x; /*dreapta care imparte planul*/
std::vector<Point> v1; v1.assign(v.begin(), v.begin() + lm + 1);
std::vector<Point> v2; v2.assign(v.begin() + lm + 1, v.end());
double dmin1 = split_plane(v1);
double dmin2 = split_plane(v2);
double dmin = dmin1;//std::min(dmin1, dmin2);
std::vector<Point> reg; /*vector de puncte delimitat de distana d*/
for(int i = lm-1; i>= 0 && abs(v[i].x - xm) < dmin; i--)
reg.push_back(v[i]);
for(int i = lm; i < v.size() && abs(xm - v[i].x) < dmin; i++)
reg.push_back(v[i]);
std::sort(reg.begin(), reg.end(), y_cmp); /*sortez dupa y*/
for(size_t i = 0; i < reg.size()-1; i++)
for(size_t k = i+1; k < reg.size() && (abs(reg[i].y - reg[k].y) < dmin); k++)
dmin = std::min(dist(reg[i], reg[k]), dmin);
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 = 1; i <= n; i++){
fin >> p.x >> p.y;
v.push_back(p);
}
std::sort(v.begin(), v.end(), x_cmp);
double dmin = split_plane(v);
fout.precision(8);
fout << dmin << '\n';
fin.close();
fout.close();
return 0;
}