Pagini recente » Cod sursa (job #2002503) | Cod sursa (job #2212591) | Cod sursa (job #1242970) | Cod sursa (job #2425315) | Cod sursa (job #2064846)
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <utility>
#include <cmath>
#define INT_MAX 1000001
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
vector < pair <int,int> > myVect;
vector < int > sideLane;
double dist(pair<int,int> a, pair <int,int> b)
{
return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}
double cmap(int left, int right)
{
//cazul in care am mai putin de un punct
if(left>=right)
{
double bestsol=INT_MAX;
return INT_MAX;
}
//2 sau 3 puncte ramase
else if (right - left <= 2)
{
double bestsol=INT_MAX;
for(int i = left; i <= right; ++i)
{
for(int j = i+1;j <= right;++j) if(dist(myVect[i] , myVect[j]) < bestsol)
bestsol=dist(myVect[i] , myVect[j]);
return bestsol;
}
}
int mid = (left + right)/2;
double bestsol = min(cmap(left,mid),cmap(mid,right));
//prelucram sirul de care se situeaza la distanta maxima la stanga si la dreapta dreptei
for(int i = mid; i >= left && myVect[mid].first-myVect[i].first <= bestsol; i--) sideLane.push_back(i);
for(int i = mid+1; i <= right && myVect[i].first-myVect[mid].first <= bestsol; i++) sideLane.push_back(i);
sort(sideLane.begin(),sideLane.end());
for(int i=0; i<sideLane.size()-1; ++i)
for(int j=i+1; j<=i+7 && j<sideLane.size(); ++j) if(dist(myVect[sideLane[i]],myVect[sideLane[j]]) < bestsol) bestsol=dist(myVect[sideLane[i]],myVect[sideLane[j]]);
return bestsol;
}
int main()
{
int n;
fin>>n;
int x,y;
for(int i=0;i<n;i++)
{
fin>>x>>y;
myVect.push_back(make_pair(x,y));
}
sort(myVect.begin(),myVect.end());
fout<<cmap(0,n-1);
}