Pagini recente » Clasament emag_2016-incepatori-2 | Cod sursa (job #1582421) | Cod sursa (job #1134199) | Cod sursa (job #2476951) | Cod sursa (job #1166975)
#include<fstream>
#include<algorithm>
#include<iomanip>
using namespace std;
struct punct
{
double x, y;
}puncte[100005],pctAux[100005];
bool SortAscX(punct a, punct b)
{
if (a.x == b.x)
return (a.y < b.y);
return (a.x<b.x);
}
bool SortAscY(punct a, punct b)
{
return (a.y < b.y);
}
double dist(punct a, punct b)
{
return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}
double rezolva(int stg, int drep)
{
//tratare caz elementar
if (drep - stg + 1 <= 3)
{
double dmin = dist(puncte[stg], puncte[stg + 1]);
for (int i = stg; i < drep; i++)
{
for (int j = i + 1; j <= drep; j++)
dmin = min(dmin, dist(puncte[i], puncte[j]));
}
return dmin;
}
double solutieStg = rezolva(stg, (stg + drep) / 2);
double solutieDrp = rezolva((stg + drep) / 2 + 1, drep);
double DminCurent = min(solutieStg, solutieDrp);
/////
int mijloc = (stg + drep) / 2;
double drepMij = (puncte[mijloc].x + puncte[mijloc+1].x) / 2;
int nrPAux=0;
for (int i = stg; i <= drep; i++)
{
if (abs(puncte[i].x - drepMij) <= DminCurent)
pctAux[++nrPAux] = puncte[i];
}
/// sortam crescator dupa y;
sort(pctAux + 1, pctAux + nrPAux + 1, SortAscY);
int i, j;
for (i = 1; i < nrPAux; i++)
{
for (j = i + 1; j<=min(nrPAux, i+7); j++)
if (DminCurent > dist(pctAux[i], pctAux[j]))
DminCurent = dist(pctAux[i], pctAux[j]);
}
return DminCurent;
}
int main()
{
unsigned int n;
ifstream inputStream("cmap.in");
ofstream outputStream("cmap.out");
inputStream >> n;
for (int i = 1; i <= n; i++)
inputStream >> puncte[i].x >> puncte[i].y;
sort(puncte + 1, puncte + n + 1, SortAscX);
outputStream <<setprecision(6)<<fixed<< rezolva(1, n);
return 0;
}