Pagini recente » Cod sursa (job #215445) | Cod sursa (job #248946) | Cod sursa (job #1471750) | Istoria paginii runda/testare_chiur/clasament | Cod sursa (job #2089056)
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;
int N;
struct punct
{
double x,y;
double dist(punct p)
{
return sqrt((this->x-p.x)*(this->x-p.x)+(this->y-p.y)*(this->y-p.y));
}
}vPuncte[100005];
bool cmp(punct p1,punct p2)
{
return p1.x<p2.x;
}
void citire()
{
scanf("%d",&N);
for(int i=1;i<=N;i++)
{
scanf("%lf%lf",&vPuncte[i].x,&vPuncte[i].y);
}
sort(vPuncte+1,vPuncte+N+1,cmp);
}
double distPeSemiplan(int st,int dr,vector <punct> deCmp)
{
if(dr-st==2)
{
return min(vPuncte[st].dist(vPuncte[dr-1]),vPuncte[st+1].dist(vPuncte[dr]));
}
if(dr-st==1)
{
return vPuncte[st].dist(vPuncte[dr]);
}
double tmp=0x3f3f3f3f;
for(int it1=0;it1<deCmp.size()-4&&deCmp.size();it1++)
for(int it2=4;it2<deCmp.size();it2++)
tmp=min(tmp,deCmp[it1].dist(deCmp[it2]));
deCmp.erase(deCmp.begin(),deCmp.end());
for(int i=(st+dr)/2-3;i<=(st+dr)/2+4;i++)
deCmp.push_back(vPuncte[i]);
return min(tmp,min(distPeSemiplan(st,(st+dr)/2,deCmp),distPeSemiplan((st+dr)/2,dr,deCmp)));
}
int main()
{
freopen("cmap.in","r",stdin);
freopen("cmap.out","w",stdout);
citire();
vector <punct> v;
printf("%lf",distPeSemiplan(1,N,v));
return 0;
}