Pagini recente » Cod sursa (job #4325) | Cod sursa (job #1475990) | Cod sursa (job #375053) | Cod sursa (job #2302168) | Cod sursa (job #2491840)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
typedef struct Point
{
int x, y;
} Point;
vector<Point> puncte;
double dist(Point p1, Point p2)
{
return double((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}
int operator<(Point& a, Point& b)
{
return a.y<b.y;
}
double distanta_minima_banda(vector<Point> &banda, double delta)
{
sort(banda.begin(),banda.end());
double minim=delta;
for (int i = 0; i < banda.size(); i++)
for (int j = i+1; j < banda.size(); j++)
{
if(abs(banda[j].y-banda[i].y)>delta)
break;
else
minim=min(minim,dist(banda[j],banda[i]));
}
return minim;
}
double distanta_minima(int st, int dr)
{
if (dr - st == 1)
return 9999999;
if (dr - st == 2)
return dist(puncte[st], puncte[st + 1]);
if (dr - st == 3)
{
return min({dist(puncte[st], puncte[st + 1]),
dist(puncte[st], puncte[st + 2]),
dist(puncte[st + 1], puncte[st + 2])});
}
int mijloc=(dr+st)/2;
double minim=min(distanta_minima(st,mijloc),distanta_minima(mijloc+1,dr));
vector<Point> banda;
for(int i=st;i<dr;i++){
if(abs(puncte[i].x-puncte[mijloc].x)<minim)
banda.push_back(puncte[i]);
}
return min(minim,distanta_minima_banda(banda,minim));
}
int main()
{
const char iname[] = "cmap.in";
const char oname[] = "cmap.out";
int n;
ifstream in(iname);
ofstream out(oname);
in >> n;
puncte.resize(n);
for (int i = 0; i < n; ++i)
{
Point p;
in >> p.x >> p.y;
puncte[i]=p;
}
in.close();
out<<sqrt(distanta_minima(0,n));
}