Pagini recente » Cod sursa (job #3185418) | Clasament testere | Cod sursa (job #2157374) | Cod sursa (job #1894638) | Cod sursa (job #1615658)
//
// 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>
float 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;
}
float distanceAB(punct A,punct B)
{
return sqrt( (A.x-B.x) * (A.x-B.x) + (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;
}
float line(std::vector<punct> a)
{
float local = 1<<30;
std::sort(a.begin(), a.end(), cmpY);
for(int i=0;i<a.size();++i)
{
//printf("\n\nA: %d %d\n",a[i].x,a[i].y);
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]));
}
}
//printf("local: %f\n",local);
return local;
}
float divide(std::vector<punct> a)
{
int mij = int((a.size()-1)/2);
if(a.size() == 1)
{
return distanceAB(a[0], a[1]);
}
else if(a.size() == 2)
{
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) ));
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 >= 0; 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);
/*for(int i=0;i<a.size();++i)
{
printf("%d\n",a[i].x);
}*/
printf("%f",divide(a));
return 0;
}