현수막 걸기 (백준 30459)

안녕하세요. 오늘은 현수막을 걸 거예요.

문제

https://www.acmicpc.net/problem/30459

아이디어

일단 말뚝을 고르는 과정은 N^2으로 구해야합니다.
그러면 빠르게 그 두 말뚝으로 최대한의 넓이를 구할 수 있어야 합니다.

그러려면 높이의 최댓값을 구해야합니다. 문제에는 삼각형이라고 되어있지만 그러면 구현이 불편해지기 때문에 직사각형이라고 생각을 한 다음에 맨 마지막에 2로 나누어서 출력해줍시다. 그러면 자연스럽게 R의 범위에도 2를 곱해주어야 합니다.

B는 모두 정수입니다. 그래서 R/d를 그대로 써도 됩니다. 이 값 이하의 값중 최대의 값을 B에서 찾은 다음에 그 값이 있다면 d*(그 값)을 최댓값과 갱신해주면 되고 없다면 그냥 스킵해주면 됩니다.

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int N, M, R, i, j;
    vector <int> A, B;

    cin >> N >> M >> R; R *= 2; //직사각형으로 통일
    for (i = 0; i < N; i++)
    {
        int x;
        cin >> x;
        A.push_back(x);
    }
    for (i = 0; i < M; i++)
    {
        int x;
        cin >> x;
        B.push_back(x);
    }
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    int mx = -1;
    for (i = 0; i < N; i++)
    {
        for (j = i + 1; j < N; j++)
        {
            int d = A[j] - A[i];
            int idx = upper_bound(B.begin(), B.end(), R / d) - B.begin() - 1;;
            if (idx == -1) //R이하인게 없다면 
                continue; //건너뛰기
            mx = max(mx, d * B[idx]); //넓이 저장
        }
    }

    if (mx == -1) cout << -1;
    else
    {
        cout << fixed;
        cout.precision(1);

        cout << (double)(mx) / 2;
    }
}

감사합니다.