Pagini recente » Cod sursa (job #2270566) | Cod sursa (job #3359356) | Monitorul de evaluare | Borderou de evaluare (job #3110881) | Cod sursa (job #3358787)
#include <fstream>
#include<bits/stdc++.h>
using namespace std;
ifstream in("cmap.in");
ofstream out("cmap.out");
#define int long double
struct punct
{
int a,b;
};
punct arr[201];
int dist(int32_t idx1,int32_t idx2)
{
return sqrt((arr[idx1].a-arr[idx2].a)*(arr[idx1].a-arr[idx2].a)+(arr[idx1].b-arr[idx2].b)*(arr[idx1].b-arr[idx2].b));
}
bool cmpa(punct c,punct d)
{
return c.a<d.a;
}
bool cmpb(punct c,punct d)
{
return c.b<d.b;
}
int vacucerescfraierilor(int32_t l,int32_t r)
{
if(r-l+1<=3)
{
int mn=4e18;
for(int i=l; i<=r; i++)
{
for(int j=i+1; j<=r; j++)
{
mn=min(mn,dist(i,j));
}
}
sort(arr+l,arr+r+1,cmpb);
return mn;
}
int32_t mid=+(r+l)/2;
int lina=arr[mid].a;
int st=vacucerescfraierilor(l,mid);
int dr=vacucerescfraierilor(mid+1,r);
int mnn=min(st,dr);
inplace_merge(arr+l,arr+mid+1,arr+r+1,cmpb);
vector<punct> inpatrat;
for(int32_t i=l; i<=r; i++)
{
if(abs(arr[i].a-lina)<mnn)
{
inpatrat.push_back(arr[i]);
}
}
for(int i=0; i<inpatrat.size(); i++)
{
for(int j=i+1; j<inpatrat.size() && inpatrat[j].b-inpatrat[i].b<mnn; j++)
{
mnn=min(mnn,sqrt((inpatrat[i].a-inpatrat[j].a)*(inpatrat[i].a-inpatrat[j].a)+(inpatrat[i].b-inpatrat[j].b)*(inpatrat[i].b-inpatrat[j].b)));
}
}
return mnn;
}
signed main()
{
int32_t n;
in>>n;
for(int32_t i=1; i<=n; i++)
{
in>>arr[i].a>>arr[i].b;
}
sort(arr+1,arr+n+1,cmpa);
out<<fixed<<setprecision(6)<<vacucerescfraierilor(1,n);
return 0;
}