Pagini recente » Cod sursa (job #2308764) | Istoria paginii runda/teest/clasament | Cod sursa (job #1433861) | Cod sursa (job #2550006) | Cod sursa (job #1166933)
//Cele mai apropiate puncte din plan
#include<fstream>
#include<algorithm>
#include<iomanip>
#include<cmath>
using namespace std;
typedef struct { double x, y; } punct;
punct a[100005],aux[100005];
int i,j,n;
bool cmp( punct a, punct b){
if (a.x==b.x) return(a.y<b.y);
else return(a.x<b.x);
}
bool cmp1( punct a, punct b){ return(a.y<b.y); }
double abss(double x) {
if (x<0) return(-x);
else return(x);
}
double dist(punct a, punct b){
return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) );
}
double solutie(int l, int r) {
//cazul banal cu 3 sau 2 puncte
if ( r-l+1<=3 ) {
double dmin=dist(a[l],a[l+1]);
for (int i=l; i<r; ++i)
for (int j=i+1; j<=r; ++j)
dmin=min(dmin,dist(a[i],a[j]));
return dmin;
}
//daca am mai multe puncte le impart in doua submultimi
int mid=(l+r)/2;
double leftmin=solutie(l,mid), rmin=solutie(mid+1,r);
double s=min(leftmin,rmin);
//acum iau punctele care se afla la distanta maxim s de drapta centrala
double xc=(a[mid].x+a[mid+1].x)/2;
int nraux=0;
for (int i=l; i<=r; ++i)
if (abss(a[i].x-xc)<=s) { ++nraux; aux[nraux]=a[i]; }
//sortez punctele respective dupa y
sort(aux+1,aux+nraux+1,cmp1);
for (int i=1; i<nraux; ++i)
for (int j=i+1; j<=min(i+7,nraux); ++j)
s=min(s, dist(aux[i],aux[j]));
return s;
}
int main(void) {
ifstream fin("cmap.in");
ofstream fout("cmap.out");
fin>>n;
for (i=1; i<=n; ++i) fin>>a[i].x>>a[i].y;
sort(a+1,a+n+1,cmp);
fout<<setprecision(6)<<fixed<<solutie(1,n);
return(0);
}