백준 문제 1027번 고층 건물 문제풀이 c++

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

1027번: 고층 건물

 

문제해석

 

N이 최대 50이므로 N^3 브루트포스 전체탐색이 가능하다.

 

예로 N=4인경우

0번째 건물과 1번째 건물이 서로 보이나 비교

0번째 건물과 2번째 건물 서로 보이나 비교

0번째 건물과 3번째 건물 서로 보이나 비교

1번째 건물과 2번째 건물 서로 보이나 비교

1번째 건물과 3번째 건물 서로 보이나 비교

2번째 건물과 3번째 건물 서로 보이나 비교

 

즉 i번째 건물 과 j번째 건물이 서로 보이려면 그 사이에 있는 i+1번째 건물부터 j-1건물(이를 k라고 두자)

세점 사이의 관계가 중요하다.

그 관계란 i점 j점 k점을 순서대로 이은 선분이 시계 방향으로 꺽여야한다.

시계방향으로 꺽이는지 판단은 예전에 ccw문제를 풀면서 작성한 코드를 그대로 가져왔다.

 

코드

 

#include <iostream>
#include <algorithm>
typedef long long int ll;
using namespace std;
ll ccw(ll x1,ll x2,ll x3,ll y1,ll y2,ll y3);
ll a[50];
ll cnt[50];
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    ll n; cin>>n;
    for(ll i=0; i<n; i++)
    {
        cin>>a[i];
    }
    for(ll i=0; i<n; i++)
    {
        for(ll j=i+1; j<n; j++)
        {
            for(ll k=i+1; k<j; k++)
            {
                if(ccw(i,j,k,a[i],a[j],a[k])==-1)
                {
                    continue;
                }
                else
                {
                    goto Label;
                }
            }
            cnt[i]++;
            cnt[j]++;
            Label: continue;
        }
    }
    ll ans=0;
    for(ll i=0; i<n; i++)
    {
        ans=max(ans,cnt[i]);
    }
    cout<<ans;
}
ll ccw(ll x1,ll x2,ll x3,ll y1,ll y2,ll y3){
    if(x1==x2)
    {
        if(x3>x1)
        {
            return -1;
        }
        else if(x3<x1)
        {
            return 1;
        }
    }
    else if(x1==x3)
    {
        if(y3<y1)
        {
            return -1;
        }
        else if(y3>y1)
        {
            return 1;
        }
    }
    else
    {
        ll a=(x1-x3)*(y1-y2);
        ll b=(x1-x2)*(y1-y3);
        if(a<b)
        {
            return 1;
        }
        else if(a>b)
        {
            return -1;
        }
    }
    return 0;
}