[BOJ/백준] 30459 - 현수막 걸기

30459번: 현수막 걸기

---

1. 말뚝 두개 선택 (N * N)

 

2. R보다 작으면서 최대인 깃대를 이분탐색으로 선택

---

---

• 제목

현수막 걸기

---

• 조건

시간 제한 : 1 초

메모리 제한 : 1024 MB 

---

• 문제

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

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

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

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

---

• 입력

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

둘째 줄에 말뚝의 위치를 나타내는 N개의 정수 Ai가 공백으로 구분되어 주어진다. ( -20,000 ≤ Ai ≤ 20,000 ) 

셋째 줄에 쿠가 가지고 있는 깃대의 길이를 나타내는 M개의 정수 Bi가 공백으로 구분되어 주어진다. ( 1 ≤ Bi ≤ 40,000 ) 

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

---

• 출력

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

---

예제 입력1	예제 출력1
3 5 23 -5 0 5 1 6 2 8 10	20.0

예제 입력2	예제 출력2
2 1 100 1 20 5	47.5

예제 입력3	예제 출력3
4 4 5 1 4 10 7 5 16 17 20	-1

---

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int R = Integer.parseInt(st.nextToken());

        int[] stake = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            stake[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(stake);

        int[] flagpole = new int[M];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            flagpole[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(flagpole);

        double answer = -1;
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                int low = 0;
                int high = M - 1;
                while(low <= high){
                    int mid = (low + high) / 2;
                    double area = (double) ((stake[j] - stake[i]) * flagpole[mid]) / 2;
                    if(area <= R){
                        low = mid + 1;
                        answer = Math.max(answer, area);
                    } else {
                        high = mid - 1;
                    }
                }
            }
        }
        System.out.println(answer == -1 ? -1 : String.format("%.1f", answer));
    }
}