원 안에 원을 가득 채우는 문제?(circle packing in a circle)

20744번: Cucumber Conundrum (acmicpc.net)

 

반지름이 s인 원 모양의 샌드위치가 있고 반지름이 r인 원 모양의 피클이 n개 있는데 

 

이 피클을 샌드위치 위에 최대한 많이 높고 싶다

 

이 때 샌드위치 면적의 최대 z%까지만 놓을 수 있고 두 피클이 서로 겹치지 않아야한다

 

최대 몇개의 피클을 놓을 수 있는가?

 

샌드위치의 면적이 $\pi * s^{2}$이고 이것의 최대 z%가 피클 x개의 넓이 $\pi * r^{2} * x$이므로

 

$$\pi * s^{2} * \frac{z}{100} >= \pi * r^{2} *x $$

 

식을 정리하면 $x <= \frac{s^{2}}{r^{2}} \frac{z}{100}$

 

사실 이것만 만족하면 되는줄 알았는데... 아니더라고

 

https://en.wikipedia.org/wiki/Circle_packing_in_a_circle

Circle packing in a circle - Wikipedia

 

 

바깥 원의 반지름과 내부 원의 반지름의 비가 조건을 만족해야하더라고

 

 

 

 

안에 채울려는 원의 반지름이 1일때 바깥 원의 반지름이 얼마여야하는지 구해놓은 표

 

예를 들어 원 4개를 가득 채울려면 안쪽 원/바깥쪽 원 = $\frac{1}{1+\sqrt{2}}$ 보다는 작아야 원이 4개이상 들어가겠지

 

첫번째 조건 $x <= \frac{s^{2}}{r^{2}} \frac{z}{100}$으로 가능한 x를 구하고

 

두번째 반지름 비 조건으로 몇개까지 채울 수 있는지 구해놓고

 

현재 가지고 있는 피클 수 n개를 구하고

 

이 세가지 값 중 최솟값이 정답이겠지

 

s,r,n,z = input().split()

s = float(s)
r = float(r)
n = int(n)
z = int(z)

v = (s**2) * (z/100) / (r**2)
v = int(v)

f = r/s

x1 = 1 + (2*(1+1/(5**(1/2))))**(1/2)
x2 = 1 + 2**(1/2)
x3 = 1 + 2/(3**(1/2))

if f <= 1/3:
    
    print(min(n,v))

elif f <= 1/x1:
    
    print(min(n,v,5))

elif f <= 1/x2:
    
    print(min(n,v,4))

elif f <= 1/x3:
    
    print(min(n,v,3))
    
elif f <= 1/2:
    
    print(min(n,v,2))

else:
    
    print(min(n,v,1))