2750801 2008-02-14 13:48:15 Accepted 2107 C++ 00:02.95 4068K C.D. 分治算法的应用。在求左和右之间的最短点对时，先把满足X坐标差值小于CurMin的点对按Y排序，然后可以剪掉Y坐标值差小于CurMin的点对。 /**//* 作者 Crux.D 日期 2008.2.14 描述 分治求最短距离点对*/#include <cstdio>#include <string>#include <cstdlib>#include <cmath>typedef struct{ double x, y;} Point;Point p[100001];int N, q[100000];int init ();double b_search ( int, int );inline double dist ( int i, int j ){ double x = sqrt ( ( p[i].x - p[j].x ) * ( p[i].x - p[j].x ) + ( p[i].y - p[j].y ) * ( p[i].y - p[j].y ) ); return x;}inline double min ( double a, double b ){ return a > b ? b : a;}int cmpx ( const void *a, const void *b ){ Point *A = ( Point * ) a, *B = ( Point * ) b; return A->x > B->x;}int cmpq ( const void *a, const void *b ){ int *A = ( int * ) a, *B = ( int * ) b; return p[*A].y > p[*B].y;}int main (){ //freopen ( "in.txt", "r", stdin ); while ( init () ) { printf ( "%0.2f\n", b_search ( 0, N - 1 ) / 2 ); } return 0;}int init (){ scanf ( "%d", &N ); int i; for ( i = 0; i < N; i ++ ) { scanf ( "%lf%lf", &p[i].x, &p[i].y ); } qsort ( p, N, sizeof ( p[0] ), cmpx ); return N;}double b_search ( int l, int r ){ if ( l == r - 1 ) { return dist ( l, r ); } else if ( l == r - 2 ) { return min ( dist ( r, l + 1 ), min ( dist ( l, r ), dist ( l, l + 1 ) ) ); } else { int mid = ( l + r ) / 2; double cur_min = min ( b_search ( l, mid ), b_search ( mid + 1, r ) ); int size = 0; int i; for ( i = mid - 1; i >= l && p[mid + 1].x - p[i].x < cur_min; i -- ) { q[size ++] = i; } for ( i = mid + 1; i <= r && p[i].x - p[mid].x < cur_min; i ++ ) { q[size ++] = i; } qsort ( q, size, sizeof ( q[0] ), cmpq ); int j; for ( i = 0; i < size - 1; i ++ ) { for ( j = i + 1; j < size && p[q[j]].y - p[q[i]].y < cur_min; j ++ ) { cur_min = min ( cur_min, dist ( q[i], q[j] ) ); } } return cur_min; }}
评论