Pagini recente » Cod sursa (job #2285518) | Cod sursa (job #1531336) | Cod sursa (job #514937) | Cod sursa (job #2323969) | Cod sursa (job #2280446)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define x first
#define y second
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
const int NMax = 100005;
pair < int, int > Puncte[NMax];
int nr_Puncte;
void Read()
{
fin >> nr_Puncte;
for(int i = 1; i <= nr_Puncte; ++i)
{
fin >> Puncte[i].x >> Puncte[i].y;
}
}
void Print(pair <int, int > vec[], int nr)
{
for(int i = 1; i <= nr; ++i)
{
fout << vec[i].x << " " << vec[i].y << "\n";
}
fout << "\n";
fout << "\n";
fout << "\n";
}
double Calc_Dist(pair < int, int > p1, pair < int, int > p2)
{
return ((double)p1.x - p2.x) * (p1.x - p2.x) + (1.0 * p1.y - p2.y) * (p1.y - p2.y);
}
double mindist = 1.0 * 0x3f3f3f3f;
int modul(int x)
{
if(x < 0)
return -x;
return x;
}
struct MyClass {
bool operator() (pair < int, int > p1, pair < int, int > p2)
{
return p1.y < p2.y;
}
} Compare;
pair < int, int > strip[NMax];
double DivideEtImpera(int st, int dr)
{
if (dr - st == 1)
{
return Calc_Dist(Puncte[st], Puncte[dr]);
}
else if(dr - st == 2)
{
double dist1 = Calc_Dist(Puncte[st], Puncte[st+1]);
dist1 = min(dist1, Calc_Dist(Puncte[st+1], Puncte[dr]));
dist1 = min(dist1, Calc_Dist(Puncte[st], Puncte[dr]));
return dist1;
}
int mij = (st + dr) / 2;
int xmin = Puncte[mij].x;
double d1 = DivideEtImpera(st, mij);
double d2 = DivideEtImpera(mij+1, dr);
d1 = min(d1, d2);
int k = 0;
for(int i = st; i <= dr; ++i)
if(modul(xmin - Puncte[i].x) < d1)
strip[++k] = Puncte[i];
sort(strip + 1, strip + k + 1, Compare);
for(int i=1; i <= k; ++i)
for(int j = 1; j <= 8; ++j)
if( i + j <= k)
{
double dist = Calc_Dist(Puncte[i], Puncte[i + j]);
d1 = min(dist, d1);
}
return d1;
}
int main()
{
Read();
sort(Puncte + 1, Puncte + nr_Puncte + 1);
fout << fixed << setprecision(6) << sqrt(DivideEtImpera(1, nr_Puncte));
return 0;
}