Pagini recente » Cod sursa (job #1409120) | Cod sursa (job #1611805) | Cod sursa (job #2902694) | Cod sursa (job #1741927) | Cod sursa (job #2071217)
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <utility>
#include <cmath>
#include <iomanip>
#define INT_MAX 1000001
using namespace std;
int ok=0;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
vector < pair <int,int> > myVect;
vector < int > sideLane;
bool cmp (const int a, const int b)
{
return myVect[a].second<myVect[b].second;
}
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 bestsol;
}
//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));
sideLane.clear();
//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);
if(ok==0)
sort(sideLane.begin(),sideLane.end(),cmp),ok=1;
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<<fixed<<setprecision(6)<<cmap(0,n-1);
}