1027번: 고층 건물

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


$O(n^2)$

i번 건물에서 j(j>i)번 건물을 보고 번호를 1씩 증가시킨다 하자.
두 건물을 이은 직선의 기울기가 지금까지의 것보다 큰 경우에만 두 건물 사이에서 서로를 볼 수 있다.

#include<cstdio>
#include<algorithm>
int n, a[50], b[50];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", a + i);
    for (int i = 0; i < n; i++) {
        double t = -9e9, m;
        for (int j = i + 1; j < n; j++) {
            m = (double)(a[j] - a[i]) / (j - i);
            if (m > t) t = m, b[i]++, b[j]++;
        }
    }
    printf("%d", *std::max_element(b, b + n));
    return 0;
}