MLE20pts求调
查看原帖
MLE20pts求调
667452
Null_in_null楼主2024/6/18 21:16
#include<bits/stdc++.h>
#define int long long
using namespace std ;
vector<int> mp[1005] ;
bool vis[1005] = {false} ;
bool o[1005] = {false} ;
bool d[1005] = {false} ;
int x[1005] = {0} ;
int y[1005] = {0} ;
int z[1005] = {0} ;
int n , h , r ;

bool dfs( int q , int fa ) {
	bool ans = false ;
	for ( int i = 1 ; i <= mp[q].size() ; i++ ) {
		if ( mp[q][i] == fa ) {
			continue ;
		}
		else {
			vis[mp[q][i]] = true ;
			if ( o[mp[q][i]] || dfs( mp[q][i] , q ) ) {
				ans = true ;
			}
		}
	}
	return ans ;
}

signed main() {
	int T ;
	cin >> T ;
	while ( T-- ) {
		for ( int i = 0 ; i <= 1004 ; i++ ) {
			mp[i].clear() ;
		}
		for ( int i = 0 ; i <= 1004 ; i++ ) {
			vis[i] = false ;
		}
		for ( int i = 0 ; i <= 1004 ; i++ ) {
			o[i] = false ;
		}
		for ( int i = 0 ; i <= 1004 ; i++ ) {
			d[i] = false ;
		}
		for ( int i = 0 ; i <= 1004 ; i++ ) {
			x[i] = 0 ;
		}
		for ( int i = 0 ; i <= 1004 ; i++ ) {
			y[i] = 0 ;
		}
		for ( int i = 0 ; i <= 1004 ; i++ ) {
			z[i] = 0 ;
		}
		cin >> n >> h >> r ;
		for ( int i = 1 ; i <= n ; i++ ) {
			cin >> x[i] >> y[i] >> z[i] ;
			if ( ( z[i] - r ) <= 0 ) {
				d[i] = true ;
			}
			if ( ( z[i] + r ) >= h ) {
				o[i] = true ;
			}
		}
		for ( int i = 1 ; i <= n ; i++ ) {
			for ( int j = i ; j <= n ; j++ ) {
				if ( ( ( x[i] - x[j] ) * ( x[i] - x[j] ) + ( y[i] - y[j] ) * ( y[i] - y[j] ) + ( z[i] - z[j] ) * ( z[i] - z[j] ) ) <= ( 2 * r ) * ( 2 * r ) ) {
					mp[i].push_back(j) ;
					mp[j].push_back(i) ;
				}
			}
		}
		bool flag = true ;
		for ( int i = 1 ; i <= n ; i++ ) {
			if ( d[i] && !vis[i] ) {
				if ( dfs( i , 0 ) ) {
					cout << "Yes" << endl ;
					flag = false ;
					break ;
				}
				else {
					continue ;
				}
			}
		}
		if ( flag ) {
			cout << "No" << endl ;
		}
	}
	return 0 ;
}

2024/6/18 21:16
加载中...