Pagini recente » Cod sursa (job #1001605) | Cod sursa (job #401586) | Cod sursa (job #346905) | Cod sursa (job #287673) | Cod sursa (job #1615710)
//
// main.cpp
// Puncte
//
// Created by Nasca Sergiu Alin on 24/02/16.
// Copyright © 2016 Nasca Sergiu Alin. All rights reserved.
//
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
double distance = 1<<30;
typedef struct punct
{
int x;
int y;
}punct;
bool cmpX(punct A,punct B)
{
return A.x < B.x;
}
bool cmpY(punct A,punct B)
{
return A.y < B.y;
}
double distanceAB(punct A,punct B)
{
return sqrt((double)(A.x-B.x)*(A.x-B.x)+(double)(A.y-B.y)*(A.y-B.y));
}
std::vector<punct> format(std::vector<punct> a, int start, int stop)
{
std::vector<punct> b;
b.assign(a.begin()+start, a.begin()+stop);
return b;
}
double line(std::vector<punct> a)
{
double local = 1<<30;
std::sort(a.begin(), a.end(), cmpY);
for(int i=0;i<a.size();++i)
{
for(int j=i+1;j<a.size();++j)
{
if(abs(a[i].y - a[j].y) > distance)break;
else local = std::min(local, distanceAB(a[i], a[j]));
}
}
return local;
}
double divide(std::vector<punct> a)
{
int mij = int((a.size()-1)/2);
if(a.size() == 2)
{
return distanceAB(a[0], a[1]);
}
else if(a.size() == 3)
{
return std::min(std::min(distanceAB(a[0], a[1]), distanceAB(a[1], a[2])), distanceAB(a[0], a[2]));
}
else
{
distance = std::min(distance, divide( format(a,0,mij+1) ));
distance = std::min(distance, divide( format(a,mij+1,int(a.size())) ));
int start,stop;
for(start = mij; std::abs(a[mij].x - a[start].x) < distance && start >= 1; start--);
for(stop = mij; std::abs(a[mij].x - a[stop].x) < distance && stop < a.size(); stop++);
distance = std::min(distance, line( format(a, start, stop) ));
}
return distance;
}
int main()
{
int n;
punct local;
std::vector<punct> a;
freopen("cmap.in", "r", stdin);
freopen("cmap.out", "w", stdout);
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%d %d",&local.x,&local.y);
a.push_back(local);
}
std::sort(a.begin(), a.end(), cmpX);
printf("%f",divide(a));
return 0;
}