Pagini recente » Istoria paginii runda/nostress8/clasament | Cod sursa (job #1440305) | Cod sursa (job #2356233) | Cod sursa (job #1775902) | Cod sursa (job #2519444)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <math.h>
using namespace std;
struct PUNCT
{
double x, y;
};
#define NMAX 99999
PUNCT p[NMAX], aux[NMAX], inter[NMAX], A, B;
double distanta(PUNCT a, PUNCT b)//distanta dintre doua puncte din plan
{
return sqrt((b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y));
}
bool cmpX(PUNCT a, PUNCT b) //sortare dup X
{
return a.x < b.x;
}
bool cmpY(PUNCT a, PUNCT b) //sortare dupa Y
{
return a.y < b.y;
}
double dist_min(int left, int right)
{
if(right - left + 1 == 3) //avem 3 puncte de o parte a medianei
{
sort(p + left, p + right, cmpY); //sortare dupa Y
double d1 = distanta(p[left], p[left + 1]);
double d2 = distanta(p[left + 1], p[left + 2]);
double d3 = distanta(p[left], p[left + 2]);
double minim = d1;
A = p[left];
B = p[left + 1];
if(d2 < minim) //aflam care sunt cele 2 puncte cele mai apropiate
{
minim = d2;
A = p[left + 1];
B = p[left + 2];
}
if(d3 < minim)
{
A = p[left];
B = p[left + 2];
minim = d3;
}
return minim;
}
if(right - left + 1 == 2) //avem doar 2 puncte de o parte a medianei
{
if(p[left].y > p[left + 1].y) //crescator
swap(p[left], p[left + 1]);
A = p[left];
B = p[left + 1];
return distanta(p[left], p[left + 1]);
}
else
{
int mijloc = (left + right) / 2; //impartim multimea de puncte a.i. sa avem n/2 puncte de fiecare parte
double mediana = p[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(p[i].y < p[j].y)
aux[k++] = p[i++];
else aux[k++] = p[j++];
while(i <= mijloc)
aux[k++] = p[i++];
while(j <= right)
aux[k++] = p[j++];
for(i = left; i <= right; i++)
{
p[i] = aux[i];
if(p[i].x - mediana <= delta && p[i].x - mediana >= -delta) // [-delta, delta]
inter[++nr] = p[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(distanta(inter[i], inter[j]) < delta) //verificam daca avem 2 puncte care sa ofere o noua distanta minima
{
delta = distanta(inter[i],inter[j]);
A = inter[i];
B = inter[j];
}
}
return delta;
}
}
int main()
{
ifstream fin("cmap.in");
ofstream fout("cmap.out");
int n, i;
fin >> n;
for(i = 1; i <= n; i++)
fin >> p[i].x >> p[i].y;
sort(p + 1 , p + n + 1, cmpX); //sortare dupa X
fout << setprecision(6) << fixed << dist_min(1, n);
return 0;
}