Pagini recente » Cod sursa (job #1875003) | Rating Mihalcea Cosmin-George (Earthequak3) | Cod sursa (job #1175987) | Cod sursa (job #2210746) | Cod sursa (job #2488059)
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("date.in");
ofstream g("date.out");
struct Point{
int x,y;
};
bool compareX(Point a, Point b){
return a.x<b.x;
}
bool compareY(Point a, Point b){
return a.y<b.y;
}
int distance(Point a, Point b){
return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
}
int minDistance(vector<Point> v, int st, int dr){
if(dr-st == 1)
return distance(v[st], v[dr]);
if(dr-st == 2){
return min({distance(v[st],v[dr-1]), distance(v[st], v[dr]), distance(v[st+1], v[dr]) });
}
int m = (st + dr)/2;
int dist1,dist2,dist_min,d;
dist1 = minDistance(v, st, m);
dist2 = minDistance(v, m+1, dr);
dist_min = min(dist1,dist2);
d = (int)ceil(sqrt(dist_min));
vector<Point> t;
for(int i=m; i<dr; i++)
if(v[i].x - v[m].x <=d)
t.push_back(v[i]);
else
break;
for(int i=m-1; i>=st; i--)
if(v[m].x - v[i].x <=d)
t.push_back(v[i]);
else
break;
sort(t.begin(),t.end(),compareY);
for(int i=0; i<t.size(); i++){
for(int j=i+1; j<=i+7 && j<t.size(); j++){
dist_min = min(dist_min, distance(t[i], t[j]));
}
}
return dist_min;
}
int main() {
int n;
vector<Point> points;
f>>n;
for(int i=0; i<n; i++){
Point p;
f>>p.x>>p.y;
points.push_back(p);
}
sort(points.begin(),points.end(),compareX);
g <<fixed<<setprecision(6) <<sqrt(minDistance(points, 0, n-1));
f.close();
g.close();
return 0;
}