현수막 걸기

시간 제한1초메모리 제한1024 MB

요약

서로 다른 말뚝 위치와 깃대 길이가 주어질 때, 두 말뚝과 깃대 하나를 골라 넓이가 R을 넘지 않으면서 최대가 되도록 하고, 불가능하면 -1을 출력한다.

난이도: 보통10점 중 6점
유형: 정렬, 이분 탐색, 수학, 완전 탐색
정답자: 아직 제출이 없습니다

문제

쿠는 KUPC를 홍보하기 위해 삼각형 모양의 거대한 현수막을 제작하고자 한다.

현수막을 걸 수 있는 지면에는 $N$ 개의 말뚝이 한 줄로 박혀 있다. 쿠는 말뚝과 미리 준비해 둔 $M$ 개의 깃대 중 하나를 이용해 현수막을 걸 수 있다. 현수막을 거는 방법은 아래와 같다.

박혀있는 말뚝 중 두 개를 골라, 두 말뚝 사이의 공간이 현수막의 밑변이 되도록 현수막을 바닥에 고정한다.
적절한 깃대를 골라, 두 말뚝 정중앙에 깃대의 길이가 현수막의 높이가 되도록 세워 삼각형 모양으로 현수막을 건다.

쿠에게는 현수막을 살 돈이 충분하지 않기 때문에, 구매할 수 있는 현수막의 최대 넓이 $R$ 을 미리 구해 두었다. 주어진 말뚝과 깃대를 활용해서 현수막을 걸고자 할 때, 쿠가 구매해서 걸 수 있는 현수막 넓이의 최댓값을 구해주자!

입력

첫째 줄에 말뚝의 개수 $N$ , 깃대의 개수 $M$ , 쿠가 살 수 있는 최대 현수막 넓이를 나타내는 정수 $R$ 이 공백으로 구분되어 주어진다. $\left( 2\leq N\leq 2\\, 000;\ 1\leq M\leq 40\\, 000;\ 1\leq R\leq 10^{9} \right)$

둘째 줄에 말뚝의 위치를 나타내는 $N$ 개의 정수 $A\_i$ 가 공백으로 구분되어 주어진다. $\left( -20\\, 000\leq A\_{i}\leq 20\\, 000 \right)$

셋째 줄에 쿠가 가지고 있는 깃대의 길이를 나타내는 $M$ 개의 정수 $B\_i$ 가 공백으로 구분되어 주어진다. $\left( 1\leq B\_{i}\leq 40\\, 000 \right)$

말뚝의 위치는 서로 다르며, 깃대의 길이도 서로 다르다.

출력

쿠가 구매해서 걸 수 있는 현수막의 최대 넓이를 출력한다. 어떻게 걸어도 현수막을 구매할 수 없는 경우 $-1$ 을 출력한다. 넓이를 출력하는 경우, 반드시 소수점 첫째 자리까지 출력한다.

예제3

예제 1
입력
```
3 5 23
-5 0 5
1 6 2 8 10
```
예상 출력
```
20.0
```
예제 2
입력
```
2 1 100
1 20
5
```
예상 출력
```
47.5
```
예제 3
입력
```
4 4 5
1 4 10 7
5 16 17 20
```
예상 출력
```
-1
```