Pagini recente » Cod sursa (job #3224733) | Cod sursa (job #2147254) | Cod sursa (job #966313) | Cod sursa (job #2103938) | Cod sursa (job #2496629)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>
using namespace std;
typedef struct Point
{
int x, y;
} Point;
vector<Point> puncte;
vector<Point> puncteY;
double dist(Point p1, Point p2)
{
return sqrt(double((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y)));
}
/*
bool compareY(Point& a, Point& b)
{
return a.y-b.y;
}
bool compareX(Point a, Point b)
{
if(a.x==b.x)
return a.y-b.y;
return a.x-b.x;
}*/
struct {
bool operator()(Point a, Point b) const
{
if(a.x==b.x)
return a.y<b.y;
return a.x<b.x;
}
} compareX;
struct {
bool operator()(Point a, Point b) const
{
return a.y<b.y;
}
} compareY;
double distanta_minima_banda(vector<Point> &banda, double delta)
{
sort(banda.begin(),banda.end(),compareY);
/*for(auto p : banda)
{
cout<<p.x<<" "<<p.y<<"\n";
}
cout<<endl;
*/
for (int i = 0; i < banda.size(); i++)
for (int j = i+1; j < banda.size(); j++)
{
if(banda[j].y-banda[i].y>=delta)
break;
else
delta=min(delta,dist(banda[j],banda[i]));
}
return delta;
}
double distanta_minima(int st, int dr)
{
if (dr - st == 0)
return 9999999;
if (dr - st == 1)
return dist(puncte[st], puncte[st + 1]);
if (dr - st == 2)
{
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;
//for punteY ===> puncteYS puncteYD
double minim=min(distanta_minima(st,mijloc),distanta_minima(mijloc+1,dr));
vector<Point> banda;
//for in punctey
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);
puncteY.resize(n);
for (int i = 0; i < n; ++i)
{
Point p;
in >> p.x >> p.y;
puncte[i]=p;
puncteY[i]=p;
}
in.close();
sort(puncte.begin(),puncte.end(),compareX);
sort(puncteY.begin(),puncteY.end(),compareY);
//sort dupa y puncteY
/*
for(auto p : puncte)
{
cout<<p.x<<" "<<p.y<<"\n";
}
cout<<endl;
*/
//apel (0,n-1, puncteY)
out<<setprecision(20)<<distanta_minima(0,n-1);
out.close();
}