[Python] 16313번 Janitor Troubles

 

https://www.acmicpc.net/problem/16313

---

 

25/06/30

 

 

간단한 기하학 문제다. (공식만 알고 있다면...)

---

 

문제 접근 방식:

 

 

원문은 이렇게 쓰여있다.

given four side lengths s1, s2, s3 and s4, find the maxiumum area of any quadrilateral that can be constructed using these lengths. A quadrilateral is a polygon with four vertices.

 

그러니까, 네 변의 길이가 주어진다면, 그 길이로 만들 수 있는 넓이가 최대인 사각형의 넓이를 구하라는 것이다.

 

https://en.wikipedia.org/wiki/Bretschneider%27s_formula

Bretschneider's formula - Wikipedia

 

이런게 있다.

 

브라마 굽타의 공식은 간혹 들어봤을 텐데, 브라마굽타의 일반화된 모습이 저 공식이다.

 

즉, 브라마굽타는 원에 외접하는 사각형일때만 적용되는 공식인 반면, 저 공식은 외접하지 않은 일반적인 사각형의 넓이를 구하는 공식이 된다.

 

그리고 그 공식의 모습은 놀랍게도 브라마 굽타와 매우 비슷한데, 이는 다음과 같다.

 

$$A = \sqrt{(s-a)(s-b)(s-c)(s-d)-abcd \cdot \cos ^2 \left( \frac{\alpha + \gamma}{2} \right)}$$

 

이게 언제 최대가 되야하냐면, $\alpha + \gamma = \pi$가 될 때 최대가 되는데, 이는 그냥 브라마굽타의 공식과 동일하다.

 

즉, 원에 외접하는 사각형이 최대인 사각형이 되는 셈이다.

 

직관적으로 생각해봐도, 네 변을 가지고 사각형을 만들때 너무 각도를 한쪽으로 좁게 만들면 넓이가 작아질 것이고, 각도가 적절히 분배될 때가 외접하게 될 때라는 사실을 느낄 수 있을 것이다.

 

이를 사용해 그냥 브라마굽타의 공식을 박아 넣으면 문제가 해결된다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 16313번 Janitor Troubles
# 브라마굽타
a, b, c, d = map(int, input().split())
s = (a+b+c+d)/2
print(((s-a)*(s-b)*(s-c)*(s-d))**.5)