Pagini recente » Profil aIexpetrescu | Cod sursa (job #2743129) | Cod sursa (job #145429) | Cod sursa (job #1511253) | Cod sursa (job #2071768)
#include <iostream>
#include <fstream>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;
struct punct{
int x,y;
};
void citire(vector<punct> &puncte)
{
ifstream in("cmap.in");
int nr;
in>>nr;
punct dummy;
while(in>>dummy.x>>dummy.y)
puncte.push_back(dummy);
in.close();
}
float distanta(punct A,punct B)
{
return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
int comparator(punct A,punct B)
{
return A.x<B.x;
}
int comparatorY(punct A,punct B)
{
return A.y<B.y;
}
void distantaMerged(int left, int m, int right, vector<punct> &puncte, punct mijloc, float &disMin)
{
vector<punct> aux;
vector<punct> bandaDistMin;
int iL=left;
int iR=m+1;
int nrElementeL=m-left+1;
int nrElementeR=right-m;
while(nrElementeR&&nrElementeL)
{
if(puncte[iL].y<puncte[iR].y)
{
if(abs(mijloc.x-puncte[iL].x)<disMin) bandaDistMin.push_back(puncte[iL]);
aux.push_back(puncte[iL]);
iL++;
nrElementeL--;
}
else
{
if(abs(mijloc.x-puncte[iR].x)<disMin) bandaDistMin.push_back(puncte[iR]);
aux.push_back(puncte[iR]);
iR++;
nrElementeR--;
}
}
if(nrElementeR)
{
while(nrElementeR)
{
if(abs(mijloc.x-puncte[iR].x)<disMin) bandaDistMin.push_back(puncte[iR]);
aux.push_back(puncte[iR]);
iR++;
nrElementeR--;
}
}
else
{
while(nrElementeL)
{
if(abs(mijloc.x-puncte[iL].x)<disMin) bandaDistMin.push_back(puncte[iL]);
aux.push_back(puncte[iL]);
iL++;
nrElementeL--;
}
}
for(int i=left;i<=right;i++)
{
puncte[i]=aux[i-left];
}
for(int i=0;i<bandaDistMin.size()-1;i++)
{
for(int j=i+1;j<bandaDistMin.size()&&j<i+8;j++)
{
float d=distanta(bandaDistMin[i],bandaDistMin[j]);
if(d<disMin&&d!=0)
{
disMin=d;
}
}
}
}
float distantaMinima(int left,int right,vector<punct> &puncte)
{
if(right-left==1)
{
if(puncte[left].y>puncte[right].y)
{
punct aux=puncte[left];
puncte[left]=puncte[right];
puncte[right]=aux;
}
return distanta(puncte[left],puncte[right]);
}
else
if(right-left==2)
{
sort(puncte.begin()+left,puncte.begin()+right,comparatorY); //3 elemente
float d1=distanta(puncte[left],puncte[left+1]);
float d2=distanta(puncte[left+1],puncte[right]);
float d3=distanta(puncte[left], puncte[right]);
if(d1<=d2&&d1<=d3) return d1;
if(d2<=d1&&d2<=d3) return d2;
if(d3<=d2&&d3<=d1) return d3;
}
else
{
int m=(left+right)/2;
punct mijloc=puncte[m];
float x=min(distantaMinima(left,m,puncte),distantaMinima(m+1,right,puncte));
distantaMerged(left,m,right,puncte,mijloc,x);
return x;
}
}
int main()
{
vector<punct> puncte;
citire(puncte);
sort(puncte.begin(),puncte.end(),comparator);
float result=distantaMinima(0,puncte.size()-1,puncte);
ofstream out("cmap.out");
out<<result;
out.close();
return 0;
}