글 읽기 - 1027번 문제 질문입니다.

chatterboy 8년 전 1

안녕하세요.

먼저, 건물들의 꼭대기를 2차원 좌표라고 생각하고 접근했습니다.

매번 건물 쌍을 뽑은 후 두 건물간의 1차 방정식을 만듭니다. 그리고

건물 쌍 사이에 있는 건물들의 높이와 비교를 하는 방식으로 풀었지만

해결하지 못했습니다. 이전에도 저와 같은 질문이 있었는데 어떻게

해야할지 몰라서 질문합니다. ㅠㅠ

#include<cstdio>
#include<algorithm>
using namespace std;
 
double a, b;
 
void makeEquation(double x1, double y1, double x2, double y2)
{
    a = (y2 - y1) / (x2 - x1);
    b = y1 - (y2 - y1) * x1 / (x2 - x1);
}
 
double f(double x)
{
    return a * x + b;
}
 
int main()
{
    int n, a[52];
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
 
    int res = 0;
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
        {
            makeEquation(i, a[i], j, a[j]);
 
            bool ok = true;
            for (int k = i + 1; k < j; k++)
                if (f(k) <= (double)a[k])
                    ok = false;
            if (ok)
                res = max(res, j - i);
        }
 
    printf("%d", res);
}