시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 123 31 16 20.513%

문제

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

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

입력

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

둘째 줄에 맨 위에 있는 별의 좌표 x1, y1과 맨 아래에 있는 별의 좌표 x2, y2가 공백을 사이에 두고 차례로 주어진다. (0 ≤  x1, y1, x2, y2 ≤ 109, y2 < y1)

그 다음 N개의 줄에 걸쳐 레일이 존재하는 y좌표 y와 x좌표의 범위 xst, xen이 차례로 주어진다. (y2 < y < y1, 0 ≤ xst < xen ≤ 109)

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

출력

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

예제 입력 1

4
2 4 0 0
1 2 4
1 2 3
2 3 5
3 2 4

예제 출력 1

4.000000000

예제 입력 2

4
5 9 9 2
7 4 11
4 7 12
6 6 10
5 3 9

예제 출력 2

0

출처

Contest > Good Bye, BOJ > Good Bye, BOJ 2019! F번

  • 문제를 만든 사람: ryute