提交时间:2024-03-21 13:42:36
运行 ID: 139122
# include <bits/stdc++.h> using namespace std ; struct nde { double begin , end ; } ; nde node [10005] ; bool cmp ( nde a , nde b ) { return a . begin != b . begin ? a . begin < b . begin :a . end < b . end ; } int main ( ) { double n , m , w , h , x ; cin >> m ; while ( m -- ) { cin >> n >> w >> h ; int k = 0 , ans = 0 ; double r = h / 2 * 1.0 , r1 , p = 0 ; for ( int i = 1 ; i <= n ; i ++ ) { cin >> x >> r1 ; if ( r1 < r ) { r = sqrt ( r * r - h * h / 4.0 ) ; node [k] . begin = max ( x - r , w ) ; node [k] . end = max ( x + r , w ) ; k ++ ; } } sort ( node + 1 , node + k + 1 , cmp ) ; while ( p < w ) { double mx = 0 ; for ( int i = 1 ; node [i] . begin <= p && i <= k ; i ++ ) { mx = max ( mx , node [i] . end - p ) ; } if ( ! mx ) { break ; } p += mx ; ans ++ ; } cout << ans << endl ; } return 0 ; }