Pagini recente » Cod sursa (job #1195303) | Borderou de evaluare (job #2691036) | Cod sursa (job #3215775) | Cod sursa (job #2177233) | Cod sursa (job #406596)
Cod sursa(job #406596)
#include<iostream>
#include<fstream.h>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<math.h>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
struct point
{
long long x,y;
};
long long lin,col,n;
double rez1,rez2,rez3;
point punct;
vector<point> v;
vector<int>::iterator it;
long long i,min=2502500,rez;
double teta(point p1, point p2)
{
return sqrt((double)((long long)((long long)p1.x-p2.x)*(p1.x-p2.x)+(long long)((long long)p1.y-p2.y)*(p1.y-p2.y)));
}
bool compare(point a, point b)
{
return (b.x>a.x);
}
double Divide_and_Conquer(long long st, long long dr,long long n)
{
double minim=2481294;
int i=0;
int j=0;
double dist;
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
if(st<=v[i].x && v[i].x<=dr && st<=v[j].x && v[j].x<=dr)
{
dist=teta(v[i],v[j]);
if(dist<minim)
minim=dist;
}
return minim;
}
long long end,mj,p=1000000,stanga,dreapta,begin;
int main()
{
fin>>n;
for(i=0;i<n;i++)
{
fin>>punct.x>>punct.y;
v.push_back(punct);
}
sort(v.begin(),v.end(),compare);
end=v[n-1].x;
begin=v[0].x;
long long mj=(begin+end)/2;
rez1=Divide_and_Conquer(begin,mj,n);
rez2=Divide_and_Conquer(mj+1,end,n);
cout<<rez1<<" "<<rez2;
if(rez1<rez2)
rez2=rez1;
else
rez1=rez2;
stanga=long (rez2);
rez3=Divide_and_Conquer(mj-stanga,mj+stanga,n);
cout<<" "<<rez3;
fout << fixed << setprecision(6);
if(rez3<rez1)
fout<<rez3;
else
fout<<rez1;
return 0;
}