11188 번 : Lifting Walls 
 11188 번 
 11188 번 - Lifting Walls 
 1 초 256 MB 16 10 10 62 . 500 % 
 The local building firm needs your help . They are building an apartment building where the walls are prefabricated and lifted in place using cranes . The building firm has located n possible locations for cranes , and needs to choose some of these so that the center of each wall can be reached by at least one crane . The cranes are quite expensive , so they want to use as few of them as possible . A crane can reach a wall if the wall ’ s center is at most a distance r away . 
 The house that is to be built is rectangular with a length ℓ and width w . 
 Find the minimum number of cranes required to reach the center of all four walls . 
 Figure C . 1 : This example corresponds to sample input 1 . 
 The first line of input contains four space - separated positive integers ℓ, w , n and r , all at most 30 . ℓ and w denote the length and width of the house , n denotes the number of possible crane locations , and r denotes the reaching distance of each crane . 
 Output one integer , the minimum number of cranes required to reach all wall segments , or Impossible if not all wall segments can be reached . 
 Contest > KTH Challenge > KTH Challenge 2012 C 번