Pagini recente » Profil Filestraffff | Cod sursa (job #2611466) | Cod sursa (job #475521) | Cod sursa (job #294090) | Cod sursa (job #2488006)
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
struct punct
{
int x,y;
};
vector<punct>pct;
int n;
bool cmp_x(punct A,punct B)
{
if(A.x==B.x) return A.y<B.y;
return A.x<B.x;
}
bool cmp_y(punct A,punct B)
{
return A.y<B.y;
}
double calc_dist(punct A,punct B)
{
return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
double search_dist_min(vector<punct>P,int left,int right)
{
double mn=1e9;
for(int i=left; i<right; i++)
for(int j=i+1; j<=right; j++)
{
//fout<<P[i].x<<" "<<P[i].y<<" "<<P[j].x<<" "<<P[j].y<<" "<<calc_dist(P[i],P[j])<<"\n";
if(calc_dist(P[i],P[j])<mn) mn=calc_dist(P[i],P[j]);
}
return mn;
}
double sol(vector<punct>P,int left,int right)
{
if(right-left<=3)
return search_dist_min(P,left,right);
int mid=(right+left)/2;
double dist_left=sol(P,left,mid);
double dist_right=sol(P,mid+1,right);
double dist_min=min(dist_left,dist_right);
int val=P[mid].x;
vector<punct>pct_closest;
int ct=0;
for(int i=left; i<=right; i++)
if(abs(P[i].x-val)<dist_min)
pct_closest.push_back(P[i]);
sort(pct_closest.begin(),pct_closest.end(),cmp_y);
double dist_min_2=1e9;
if(pct_closest.size()>=8)
{
for(int i=0; i<=pct_closest.size()-7-1; i++)
for(int j=i+1; j<=i+7; j++)
dist_min_2=min(calc_dist(pct_closest[i],pct_closest[j]),dist_min_2);
}
else
{
for(int j=1; j<pct_closest.size(); j++)
dist_min_2=min(calc_dist(pct_closest[0],pct_closest[j]),dist_min_2);
}
//fout<<dist_min<<" "<<dist_min_2<<"\n";*/
return min(dist_min,dist_min_2);
}
int main()
{
fin>>n;
for(int i=0; i<n; i++)
{
punct p;
fin>>p.x>>p.y;
pct.push_back(p);
}
sort(pct.begin(),pct.end(),cmp_x);
fout<<sol(pct,0,n-1);
return 0;
}