Pagini recente » Cod sursa (job #2342984) | Cod sursa (job #2273376) | Cod sursa (job #2805856) | Istoria paginii runda/preitm2016/clasament | Cod sursa (job #1166947)
//Cele mai apropiate puncte din plan
#include<fstream>
#include<algorithm>
#include<iomanip>
#include<cmath>
using namespace std;
typedef struct { int 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]));
sort(a+l,a+r+1,cmp1);
return dmin;
}
//daca am mai multe puncte le impart in doua submultimi
int mid=(l+r)/2;
double xc=(a[mid].x+a[mid+1].x)/2;
double leftmin=solutie(l,mid), rmin=solutie(mid+1,r);
double s=min(leftmin,rmin);
//interclasez partea stinga si partea dreapta in a, care sunt sortate dupa y
int p1=l, p2=mid+1;
for (int i=1; i<=(r-l+1); ++i) {
if (p1<=mid&&p2<=r&&a[p1].y<=a[p2].y) { aux[i]=a[p1]; ++p1; }
else if (p1<=mid&&p2<=r&&a[p1].y>a[p2].y) { aux[i]=a[p2]; ++p2; }
else if (p1>mid) { aux[i]=a[p2]; ++p2; }
else { aux[i]=a[p1]; ++p1; }
}
for (int i=l; i<=r; ++i) a[i]=aux[i-l+1];
//acum iau punctele care se afla la distanta maxim s de drapta centrala
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);
}