Pagini recente » Cod sursa (job #3123675) | Cod sursa (job #1429583) | Cod sursa (job #789380) | Cod sursa (job #796068) | Cod sursa (job #2519605)
// Problema 4 Varianta 3 Simionov Marius Daniel 242
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <math.h>
using namespace std;
#define max 99999
struct point
{
double x, y;
};
point puncte[max], aux[max], inter[max], a, b;
double distance(point a, point b)
{
return sqrt((b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y));
}
bool cmpX(point a, point b)
{
return a.x < b.x;
}
bool cmpY(point a, point b)
{
return a.y < b.y;
}
double dist_min(int left, int right)
{
if (right - left + 1 == 3) //avem 3 puncte
{
sort(puncte + left, puncte + right, cmpY);
double d1 = distance(puncte[left], puncte[left + 1]);
double d2 = distance(puncte[left + 1], puncte[left + 2]);
double d3 = distance(puncte[left], puncte[left + 2]);
double minim = d1;
a = puncte[left];
b = puncte[left + 1];
if (d2 < minim) //aflam care sunt cele 2 puncte cele mai apropiate
{
minim = d2;
a = puncte[left + 1];
b = puncte[left + 2];
}
if (d3 < minim)
{
a = puncte[left];
b = puncte[left + 2];
minim = d3;
}
return minim;
}
if (right - left + 1 == 2) //avem doar 2 puncte
{
if (puncte[left].y > puncte[left + 1].y) //crescator
swap(puncte[left], puncte[left + 1]);
a = puncte[left];
b = puncte[left + 1];
return distance(puncte[left], puncte[left + 1]);
}
else // avem mai mult de 3 puncte
{
int mijloc = (left + right) / 2; //impartim multimea de puncte a.i. sa avem n/2 puncte de fiecare parte
double mediana = puncte[mijloc].x;
double delta = min(dist_min(left, mijloc), dist_min(mijloc + 1, right));//apelam functia recursiv, pentru a imparti in subprobleme cat mai mici
int nr = 0, i, j, k;
//sortam prin interclasare(dupa valoarea ordonatei, y) punctele aflate de ambele parti ale medianei
i = left;
k = left;
j = mijloc + 1;
while (i <= mijloc && j <= right)
if (puncte[i].y < puncte[j].y)
aux[k++] = puncte[i++];
else aux[k++] = puncte[j++];
while (i <= mijloc)
aux[k++] = puncte[i++];
while (j <= right)
aux[k++] = puncte[j++];
for (i = left; i <= right; i++)
{
puncte[i] = aux[i];
if (puncte[i].x - mediana <= delta && puncte[i].x - mediana >= -delta) // [-delta, delta]
inter[++nr] = puncte[i]; //selectam doar punctele care se afla la o distanta de cel mult delta fata de mediana trasata
}
for (i = 1; i <= nr; i++)
{
int nr_vecini = min(nr, i + 7); //stim ca este suficient sa verificam cu urmatorii 7 vecini
for (j = i + 1; j <= nr_vecini; j++)
if (distance(inter[i], inter[j]) < delta) //verificam daca avem 2 puncte care sa ofere o noua distanta minima
{
delta = distance(inter[i], inter[j]);
a = inter[i];
b = inter[j];
}
}
return delta;
}
}
int main()
{
ifstream fin("cmap.in");
ofstream fout("cmap.out");
int n, index;
fin >> n;
for (index = 0; index < n; index++)
fin >> puncte[index].x >> puncte[index].y;
sort(puncte, puncte + n, cmpX);
//fout << "Distanta minima este: "<<setprecision(6) << fixed << dist_min(0, n)<<"\n";
//fout << "Punctele cele mai apropiate sunt de A( " << a.x << " , " << a.y << " ) si B( " << b.x << " , " << " ).";
fout << setprecision(6) << fixed << dist_min(0, n);
return 0;
}