Pagini recente » Cod sursa (job #387228) | Cod sursa (job #2902607) | Cod sursa (job #1432023) | Cod sursa (job #1791976) | Cod sursa (job #1041699)
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
struct punct
{
long x;
long y;
};
bool punct_cmp(punct prim,punct doilea)
{
return (prim.x < doilea.x);
}
long maxim;
int n;
punct *vector_puncte;
punct *vector2_puncte;
inline double distanta(punct primul, punct doilea)
{
return sqrt((double)(primul.x - doilea.x)*(primul.x - doilea.x) + (double)(primul.y - doilea.y)*(primul.y - doilea.y));
}
inline void combina(punct *de_combinat,int primul, int ultimul)
{
const int mijloc = (primul + ultimul) / 2;
int set_1_start = primul;
int set_1_final = mijloc;
int set_2_start = mijloc+1;
int set_2_final = ultimul;
vector<punct>ordonat;
ordonat.reserve(ultimul - primul);
while (set_1_start <= set_1_final && set_2_start <=set_2_final)
{
if (de_combinat[set_1_start].y < de_combinat[set_2_start].y)
{
ordonat.push_back(de_combinat[set_1_start]);
++set_1_start;
}
else
{
ordonat.push_back(de_combinat[set_2_start]);
++set_2_start;
}
}
while (set_1_start <= set_1_final)
{
ordonat.push_back(de_combinat[set_1_start]);
++set_1_start;
}
while (set_2_start <= set_2_final)
{
ordonat.push_back(de_combinat[set_2_start]);
++set_2_start;
}
int j = 0;
for(vector<punct>::iterator it = ordonat.begin();it != ordonat.end();++it)
{
de_combinat[primul + j] = *it;
++j;
}
}
double distanta_minima(int primul, int ultimul)
{
if (primul == ultimul)
return maxim;
if (ultimul == primul + 1)
{
if (vector2_puncte[primul].y > vector2_puncte[ultimul].y)
swap(vector2_puncte[primul], vector2_puncte[ultimul]);
return distanta(vector2_puncte[primul], vector2_puncte[ultimul]);
}
if(ultimul == primul + 2)
{
if(vector2_puncte[primul + 1].y < vector2_puncte[primul].y)
if(vector2_puncte[primul + 1].y < vector2_puncte[primul].y)
swap(vector2_puncte[primul],vector2_puncte[primul + 1]);
if(vector2_puncte[ultimul].y < vector2_puncte[ultimul - 1].y)
swap(vector2_puncte[ultimul],vector2_puncte[ultimul - 1]);
return min(min(distanta(vector2_puncte[primul],vector2_puncte[primul + 1]),distanta(vector2_puncte[primul],vector2_puncte[ultimul])),distanta(vector2_puncte[ultimul - 1],vector2_puncte[ultimul]));
}
combina(vector2_puncte,primul, ultimul);
int mijloc = (primul + ultimul)/2;
double distanta_min = min(distanta_minima(primul, mijloc), distanta_minima(mijloc + 1, ultimul));
punct *curent = new punct[ultimul - primul + 1];
int k = 0;
for (int i=primul; i<=ultimul; i++)
if (abs(vector2_puncte[i].x - vector_puncte[mijloc].x) <= (long)distanta_min)
{
curent[k] = vector2_puncte[i];
++k;
}
for (int i=0; i<k; i++)
for (int j = i+1; j <= i+7 && j < k; j++)
if (distanta(curent[i], curent[j]) < distanta_min)
distanta_min = distanta(curent[i], curent[j]);
return distanta_min;
}
int main()
{
ifstream f("cmap.in");
f>>n;
vector_puncte = new punct[n];
vector2_puncte = new punct[n];
for (int i=0; i < n; i++)
{
f>>vector_puncte[i].x;
f>>vector_puncte[i].y;
}
f.close();
maxim = distanta(vector_puncte[0],vector_puncte[1]);
sort(vector_puncte,vector_puncte+n,punct_cmp);
for (int i=0; i < n; i++)
vector2_puncte[i] = vector_puncte[i];
ofstream g("cmap.out");
g<<distanta_minima(0, --n);
g.close();
return 0;
}