18252번 - 별이 빛나는 밤에 스페셜 저지

 준겸이는 별을 굉장히 좋아한다! 그래서 준겸이는 연말을 맞아 걸어둘 밤하늘 무늬 장식판에 별 모양 장식물을 달아 예쁘게 장식하려고 한다. 장식판은 직사각형 모양으로, 위쪽 변과 아래쪽 변 위에 별 모양 장식물을 각각 하나씩 달아 벽에 고정시킨다.  준겸이는 조금 더 예쁜 장식판을 만들기 위해서, 고정판에 레일을 달아 별이 움직일 수 있게 만들었다. 하지만 레일을 잘못 달면 균형이 맞지 않을 수도 있으므로, 레일은 장식판의 끄트머리와 닿지 않으면서 밑변과 평행하게 달기로 하였다. 또한 각 레일 위를 움직일 수 있는 별은 하나씩이고, 모든 레일에는 별이 반드시 달려 있다. 레일은 서로 겹칠 수 있지만, 별은 각 레일 위에서 독립적으로 움직임에 유의하자.

인구는 준겸이의 집에 놀러 왔다가 우연히 준겸이의 장식판을 보게 되었다. 그런데, 깔끔한 것을 좋아하는 인구는 별의 배치가 너무 난잡하다는 생각을 하게 되었다. 인구는 미니멀리즘을 정말 좋아해서, 세 별을 골라 만들 수 있는 삼각형의 넓이가 작을수록 기분이 정말 좋을 것이다. 준겸이는 그런 인구를 위해 별을 레일 위에서 적절하게 움직여, 임의의 세 별을 골라 만든 삼각형 넓이의 최댓값이 가능한 한 작도록 별을 배치하려고 한다. 준겸이와 같이 별을 배치해 보자!

첫째 줄에 레일의 개수 N이 주어진다. (1 ≤ N ≤ 10,000)

둘째 줄에 맨 위에 있는 별의 좌표 x₁, y₁과 맨 아래에 있는 별의 좌표 x₂, y₂가 공백을 사이에 두고 차례로 주어진다. (0 ≤  x₁, y₁, x₂, y₂ ≤ 10⁹, y₂ < y₁)

그 다음 N개의 줄에 걸쳐 레일이 존재하는 y좌표 y와 x좌표의 범위 x_st, x_en이 차례로 주어진다. (y₂ < y < y₁, 0 ≤ x_st < x_en ≤ 10⁹)

주어지는 모든 좌표는 정수이다.

첫째 줄에 삼각형 넓이의 최댓값이 가능한 한 작도록 별을 배치했을 때 삼각형 넓이의 최댓값을 출력한다. 모범 답안과의 절대/상대 오차가 10^-6 이하인 경우 정답으로 인정된다.