P1429 平面最近点对(加强版)求助TAT....
查看原帖
P1429 平面最近点对(加强版)求助TAT....
217600
立华奏Kanade楼主2020/7/9 19:45

求助!!TwT! l,r是用数组下标

#include<bits/stdc++.h>
using namespace std;
int n;
struct node{
    double x , y , id;
}e[200005];
int cmp( node x , node y ){
    if( x.x < y.x ) return 1;
    return 0;
}
double pf( int x ){
    return fabs( x * x );
}
double jl( int a , int b ){
    double x1 = e[a].x , y1 = e[a].y;
    double x2 = e[b].x , y2 = e[b].y;
    return 1.0*sqrt( pf( x1 - x2 )  + pf( y1 - y2 ) );
}
double fz( int l , int r ){
    //cout << l << " " << r << " " << jl( l , r ) << endl;
    if( l == r ) return 99999999;
    if( l == r - 1 ) return jl( l , r );
    int mid = ( l + r ) >> 1;
    int s[200005];
    int tot = 0;
    double d;
    d = min( fz( l , mid ) , fz( mid + 1 , r ) );
    for( int i = l ; i <= r ; i++ ){
        if( fabs( e[i].x - e[mid].x ) > d ) continue;
        s[++tot] = i;
    }
    for( int i = 1 ; i <= tot ; i++ ){
        for( int j = i + 1 ; j <= tot ; j++ ){
            d = min( d , jl( s[i] , s[j] ) );
        }
    }
    return d;
}
int main(){
    cin >> n;
    for( int i = 1 ; i <= n ; i++ )// double lf 
        scanf( "%lf %lf" , &e[i].x , &e[i].y );
    sort( e + 1 , e + n + 1 , cmp );
    cout << fixed << setprecision(4) << fz( 1 , n ) << endl;
    //cout <<  fz( 1 , n ) << endl;
    return 0;
}
2020/7/9 19:45
加载中...