Pagini recente » Cod sursa (job #1655800) | Cod sursa (job #1903711) | Cod sursa (job #1847364) | Cod sursa (job #2911100) | Cod sursa (job #2970258)
#include <iostream>
#include <fstream>
#include <set>
#include <algorithm>
#include <iterator>
#include <math.h>
#define MAXN 100000
#define MAXVAL 1000000000
using namespace std;
struct Point{
double x;
double y;
};
long double getDistance(Point p1, Point p2){
double xdif = p1.x - p2.x;
double ydif = p1.y - p2.y;
return sqrt(xdif * xdif + ydif * ydif);
}
bool xComp(Point a, Point b){ // a < b
return a.x < b.x;
}
bool yComp(Point a, Point b){ // a < b
return a.y < b.y;
}
set<Point, decltype(yComp)*> s(yComp);
Point p[MAXN];
int main(){
int n, i, j;
double min;
ifstream fin ("cmap.in");
fin >> n;
for(i = 0; i < n; i ++){
fin >> p[i].x >> p[i].y;
}
fin.close();
sort(p, p + n, xComp);
min = MAXVAL;
s.insert(p[0]);
j = 0;
for(i = 1; i < n; i ++){
while(p[i].x - p[j].x > min){
s.erase(p[j]);
j ++;
}
auto lw = s.lower_bound({p[0].x, p[i].y - min});
while(lw != s.end() && lw->y < p[i].y + min){
double dist = getDistance(*lw, p[i]);
if(dist < min)
min = dist;
lw ++;
}
s.insert(p[i]);
}
FILE *fout = fopen("cmap.out", "w");
fprintf(fout, "%lf\n", min);
fclose(fout);
return 0;
}