// #define _GLIBCXX_DEBUG #ifndef DEBUG #pragma GCC optimize ( "O3" ) #pragma GCC optimize( "unroll-loops" ) #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" ) #endif #include using namespace std; using ll = long long; #define TYPE_OF( VAR ) remove_const::type >::type #define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ) #define CEXPR( LL , BOUND , VALUE ) constexpr const LL BOUND = VALUE #define CIN( LL , A ) LL A; cin >> A #define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) ) #define CIN_ASSERT( A , MIN , MAX ) CIN( TYPE_OF( MAX ) , A ); ASSERT( A , MIN , MAX ) #define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( TYPE_OF( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) #define QUIT return 0 #define COUT( ANSWER ) cout << ( ANSWER ) << "\n" #define RETURN( ANSWER ) COUT( ANSWER ); QUIT template class PairForDijkstra { private: T m_t; int m_i; public: inline PairForDijkstra( const T& t = T() , const int& i = 0 ); inline void Set( const T& t ); inline const T& Get() const noexcept; inline const int& index() const noexcept; inline bool operator<( const PairForDijkstra& t ) const; }; // (T,m_T:T^2->T,e_T:1->T)がbool operator<(const T&,const T&)に関して // 順序モノイドでありdの値がe_T()以上である場合にのみサポート。 template T Dijkstra( const T ( &d )[size_max][size_max] , const int& i_start , const int& i_final , const int& size , const T& weight_max , list& path ); template inline PairForDijkstra::PairForDijkstra( const T& t , const int& i ) : m_t( t ) , m_i( i ) {} template inline void PairForDijkstra::Set( const T& t ) { m_t = t; } template inline const T& PairForDijkstra::Get() const noexcept { return m_t; } template inline const int& PairForDijkstra::index() const noexcept { return m_i; } template inline bool PairForDijkstra::operator<( const PairForDijkstra& t ) const { return m_t < t.m_t ? true : t.m_t < m_t ? false : m_i < t.m_i; } template T Dijkstra( const T ( &d )[size_max][size_max] , const int& i_start , const int& i_final , const int& size , const T& weight_max , list& path ) { set > vertex{}; for( int i = 0 ; i < size ; i++ ){ vertex.insert( PairForDijkstra( i == i_start ? e_T() : weight_max , i ) ); } T weight[size_max] = {}; int prev[size_max] = {}; while( ! vertex.empty() ){ auto itr = vertex.begin() , end = vertex.end(); PairForDijkstra v = *itr; const T& t = v.Get(); const int& i = v.index(); const T ( &di )[size_max] = d[i]; weight[i] = t; if( i == i_final ){ break; } itr = vertex.erase( itr ); list > changed_vertex{}; while( itr != end ){ const T& weight_curr = itr->Get(); const T weight_temp = m_T( t , di[itr->index()] ); if( weight_curr > weight_temp ){ const int i_curr = itr->index(); prev[i_curr] = i; itr = vertex.erase( itr ); changed_vertex.push_back( PairForDijkstra( weight_temp , i_curr ) ); } else { itr++; } } for( auto itr_changed = changed_vertex.begin() , end_changed = changed_vertex.end() ; itr_changed != end_changed ; itr_changed++ ){ vertex.insert( *itr_changed ); } } int i = i_final; while( i != i_start ){ path.push_front( i ); i = prev[i]; } path.push_front( i_start ); return weight[ i_final ]; } inline ll m( const ll& t0 , const ll& t1 ) { return max( t0 , t1 ); } inline const ll& e() { static const ll z{}; return z; } int main() { UNTIE; CEXPR( int , bound_N , 800 ); CIN_ASSERT( N , 2 , bound_N ); CEXPR( int , bound_XY , 20000 ); CEXPR( int , bound_T , 1000000000 ); static int P[bound_N][4]; FOR( i , 0 , N ){ CIN_ASSERT( X , -bound_XY , bound_XY ); CIN_ASSERT( Y , -bound_XY , bound_XY ); CIN_ASSERT( T , 1 , bound_T ); int ( &Pi )[4] = P[i]; Pi[0] = X * X + Y * Y; Pi[1] = X; Pi[2] = Y; Pi[3] = T; } static ll d[bound_N][bound_N]; FOR( i , 0 , N ){ int ( &Pi )[4] = P[i]; ll ( &di )[bound_N] = d[i]; FOR( j , 0 , N ){ int ( &Pj )[4] = P[j]; if( Pi[3] == Pj[3] ){ ll X = Pj[1] - Pi[1]; ll Y = Pj[2] - Pi[2]; di[j] = X * X + Y * Y; } else { ll s = 4 * Pi[0] *Pj[0]; ll r = sqrt( s ) + 1; while( s < r * r ){ r--; } di[j] = Pi[0] - r + Pj[0]; } } } list dummy{}; ll answer = Dijkstra( d , 0 , N - 1 , N , 3200000001 , dummy ); RETURN( answer ); }