Pagini recente » Cod sursa (job #1939211) | Cod sursa (job #3149986) | Cod sursa (job #2051011) | Cod sursa (job #2679171) | Cod sursa (job #3167991)
#include <bits/stdc++.h>
#define punct pair<int,int>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
punct v[100010];
set<punct>M;
int i,n,a,b,k;
double d,dist(punct,punct);
int main()
{
/// se citesc punctele
f>>n;
for(i=0;i<n;i++)
{
f>>a>>b;
v[i]=make_pair(a,b);
}
/// se sorteaza dupa x
sort(v,v+n);
/// se seteaza solutia "d" la "infinit"
d=2000000001.0*sqrt(2.0);
/// se adauga intr-un set de puncte, sotrat dupa y primul punct din stanga
M.insert(make_pair(v[0].second,v[0].first));
/// se parcurg punctele spre dreapta
for(i=1;i<n;i++)
{
/// la fiecare punct
/// elimin din set punctele situate "prea departe" pe orizontala fata de punctul curent
/// mai precis se elimina orice punct care pe orizontala are distanta
/// mai mare decat d fata de punctul curent !!!
for(;(double)(v[i].first-v[k].first)>d;k++)
M.erase(make_pair(v[k].second,v[k].first));
/// acum in set au ramas puncte pe o banda vericala de latime < d cu latura dreapta
/// in punctul curent
punct P=make_pair(v[i].second,v[i].first);
/// iau punctul curent dar schimb X cu Y ( asa sunt puse punctele in set)
/// is=iterator la primul punct din set care se afla la mai mult de
/// Y_curent - d ( adica cu cel mult d mai jos)
set<punct>::iterator
is=M.lower_bound(make_pair((int)(P.first-d-1),-1000000001));
/// acum parcurg elementele din set pana la cel mult Y_curent + d
/// oricare astfel de punct are posibilitatea sa imbunatateasca solutia (sa micsoreze d)
for(;is!=M.end()&&(double)(is->first-P.first)<=d;is++)
d=min(d,dist(*is,P));
/// dupa ce am procesat punctul curent il inserez si pe el in set
M.insert(P);
}
g<<fixed<<setprecision(10)<<d;
return 0;
}
double dist(punct A,punct B)
{
double
xa=(double)A.first,
xb=(double)B.first,
ya=(double)A.second,
yb=(double)B.second;
return sqrt((xa-xb)*(xa-xb)+(ya-yb)*(ya-yb));
}
/// BOX care fata de punctul curent se extinde
/// d spre stanga
/// d in jos
/// d in sus
/// daca e sa am o distanta mai buna cu punctul curent atunci ea e fata de un
/// punct situat pe acel BOX
/// se determina punctele din BOX ca o zona dintr-un set de puncte
/// sortat dupa Y si care contine doar puncte situate la cel mult distanta d
/// in stanga fata de X-ul punctului curent !!!
// | |
// | |
// | |
// |-----------| y+d
// | |
// | |
// | |
// | |
// | |
// < -------- P(x,y)
// | |
// | |
// | |
// | |
// | |
// |___________| y-d
// | |
// | |
// | |