백준 1027. 고층 건물

tose33 2022. 12. 20. 14:06

1027번: 고층 건물

세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작)

www.acmicpc.net

두 건물의 두 옥상을 점으로 생각하면 두 점의 좌표가 주어지므로 직선의 방정식을 구할수 있다.

y - y1 = {(y2 - y1) / (x2 - x1)} * (x - x1)

빌딩의 갯수는 최대 50 개이므로 3중 반복문으로 모조리 탐색해보면 된다.

i 빌딩과 j 빌딩 의 직선의 방정식을 구한후, k 빌딩의 x좌표를 대입해서 얻은 y 값이 k 빌딩의 높이 보다 작거나 같으면, k 빌딩이 i와 j 빌딩의 시야를 막는다고 생각할수 있으므로 i건물은 j건물을 볼수 없다.