페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#6346
스페셜 저지

Almost Aligned 1.5s 1024MB

문제

곧 유성우가 내립니다! 열정적인 천문 사진작가인 당신은 현상의 일부가 될 모든 유성을 한 장의 사진으로 찍고 싶어합니다. 그뿐만 아니라, 가능한 가장 좋은 사진을 찍고 싶어합니다. 사진의 영역이 작을수록 사진이 더 좋다는 것을 알고 있습니다. 하지만 모든 유성을 포착하기 위해 사진을 얼마나 작게 만들 수 있을까요?

카메라 뷰의 직사각형 영역은 무엇이든 사진을 찍을 수 있지만, 카메라를 회전할 수는 없습니다. 즉, 사진은 축에 맞춰진 직사각형이면 됩니다. 유성은 끊임없이 움직입니다. 목표는 가능한 가장 작은 직사각형으로 모든 유성을 포착할 수 있는 시점 t를 찾는 것입니다. 사진은 테두리에 있는 유성을 포함하여 직사각형 내의 모든 유성을 포착합니다.


입력

첫 번째 줄에는 정수 N ( 1 ≤ N ≤ 10^6 )이 포함됩니다. 이는 유성의 수를 나타냅니다.

다음의 각각 N줄에는 4개의 정수로 구성된 유성의 위치와 속도를 설명하는 변수 x, y, V_X, V_y ( -10^9 ≤ X, Y, V_X, V_Y ≤ 10^9 )가 주어집니다. 정확히는, 카메라에서 보는 유성의 위치는 시각 t (t\ge0)에 ((X + t \cdot V_X, Y + t \cdot V_Y)입니다. t < 0일때 운석의 위치는 알 수 없습니다.


출력

한 번에 모든 유성을 포함하는 축 정렬 사각형의 최소 면적을 갖는 시각 t (t ≥ 0)를 첫 줄에 출력합니다. 출력의 절대 또는 상대 오류는 10^{-9} 이하여야 합니다.


예제 #1

4
0 0 10 10
0 0 10 10
10 10 -10 -10
10 0 -20 0
22.2222222222222

예제 #2

3
0 -1 0 2
1 1 1 1
-1 1 -1 1
0

예제 #3

3
0 -1 0 -2
1 1 1 1
-1 1 -1 1
4

예제 #4

1
0 0 0 0
0

출처

The 2024 ICPC Latin America Championship A번

로그인해야 코드를 작성할 수 있어요.