Pagini recente » Cod sursa (job #1434613) | Cod sursa (job #2543511) | Cod sursa (job #3270667) | Cod sursa (job #469986) | Cod sursa (job #787143)
Cod sursa(job #787143)
#include <fstream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <iomanip>
#define MAXN 100005
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
struct punct{
int x,y;};
int i,j,n;
punct p[MAXN],p1,p2,p3;
double d,mn2;
vector<punct> v;
bool comp1(punct p11,punct p22);
bool comp2(punct p11,punct p22);
double distmin(int a, int b);
int main()
{
f>>n;
for(i=1;i<=n;i++)
f>>p[i].x>>p[i].y;
sort(p+1,p+n+1,comp1);
g<<fixed<<setprecision(7)<<distmin(1,n)<<'\n';
f.close();
g.close();
return 0;
}
bool comp1(punct p11,punct p22){
return p11.x<p22.x;}
bool comp2(punct p11,punct p22){
return p11.y<p22.y;}
double distmin(int a, int b){
double mn;
int mij;
if(b-a+1==3){
p1=p[a];
p2=p[a+1];
p3=p[b];
mn=sqrt(double(1LL*(p2.x-p1.x)*(p2.x-p1.x)+1LL*(p2.y-p1.y)*(p2.y-p1.y)));
d=sqrt(double(1LL*(p2.x-p3.x)*(p2.x-p3.x)+1LL*(p2.y-p3.y)*(p2.y-p3.y)));
if(d<mn)
mn=d;
d=sqrt(double(1LL*(p3.x-p1.x)*(p3.x-p1.x)+1LL*(p3.y-p1.y)*(p3.y-p1.y)));
if(d<mn)
mn=d;
return mn;}
if(b-a+1==2)
return sqrt(double(1LL*(p[a].x-p[b].x)*(p[a].x-p[b].x)+1LL*(p[a].y-p[b].y)*(p[a].y-p[b].y)));
mij=(a+b)/2;
mn=distmin(a,mij);
d=distmin(mij+1,b);
if(d<mn)
mn=d;
mn2=mn;
v.clear();
for(i=mij;i>=a&&p[mij].x-p[i].x<mn;i--)
v.push_back(p[i]);
for(i=mij+1;i<=b&&p[i].x-p[mij].x<mn;i++)
v.push_back(p[i]);
sort(v.begin(),v.end(),comp2);
for(i=0;i<v.size()-1;i++)
for(j=i+1;j<v.size()&&v[j].y-v[i].y<mn;j++){
d=sqrt(double(1LL*(v[i].x-v[j].x)*(v[i].x-v[j].x)+1LL*(v[i].y-v[j].y)*(v[i].y-v[j].y)));
if(d<mn2)
mn2=d;}
return mn2;}