Pagini recente » Cod sursa (job #2316909) | Cod sursa (job #3173092) | Cod sursa (job #2169773) | Cod sursa (job #805869) | Cod sursa (job #1831528)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
struct point{
int x, y;
};
int n;
vector<point> points;
vector<point> points2;
void in(){
ifstream fin("cmap.in");
fin >> n;
for (int i = 0; i < n; i++)
{
point p;
fin >> p.x >> p.y;
points.push_back(p);
}
}
bool lessX(point a, point b){
return a.x < b.x;
}
bool lessY(point a, point b){
return a.y < b.y;
}
double dist(point a, point b){
return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}
double minDist(int & s, int & e){
if (e - s == 1){
//2 points
return dist(points[s], points[e]);
}
else if (e - s == 2){
//3 points
double d12 = dist(points[s], points[s + 1]);
double d23 = dist(points[s + 1], points[e]);
double d13 = dist(points[s], points[e]);
double d = min(d12, min(d23, d13));
if (d == d12){
e = s + 1;
}
else if (d == d23)
{
s = s + 1;
}
return d;
}
else{
int mid = (e + s) / 2;
int mid2 = mid + 1;
double d1 = minDist(s, mid);
double d2 = minDist(mid2, e);
if (d1 < d2){
e = mid;
}
else s = mid2;
return min(d1, d2);
}
}
int main(){
in();
points2 = points;
sort(points.begin(), points.end(), lessX);
int a = 0, b = n-1;
double d = minDist(a, b);
ofstream f("cmap.out");
f << fixed << setprecision(6) << d;
return 0;
}