백준 1027 고층 건물 C++ #Math

 A와 B 사이에 겹치는 건물이 있는지 확인하는 과정에서 "두 점 사이의 직선" 공식을 이용해서 A와 B사이에 있는 모든 건물의 높이를 계산하여 푸는 과정을 이용했다.

여기서 (double) 범벅을 한 이 코드에서 j가 자꾸 잘 못 구해지는 버그가 있었다.  A와 B건물 사이의 i번째 건물의 높이가 A와 B의 지붕을 연결한 선에 겹치지 않는지 검사하기 위해서 아래 공식을 사용한 것인데, j의 계산이 잘 되지 않았다 . 

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

// 고층 빌딩
/*
	15
	1 5 3 2 6 3 2 6 4 2 5 7 3 1 5
*/

vector<int> height ;

// 빌딩 A(x1, y1)이 빌딩 B(x2, y2)를 볼 수 있는 지 확인하는 함수
bool isOverlap(int x1, int y1, int x2, int y2) {

	for (int i = 1; i < height.size(); i++) {
		if (x1 == i || x2 == i){ // A 혹은 B 빌딩이면 패스
			continue;
		}

		if ((x1 < i && i < x2) || (x1 > i && i > x2)) { // 빌딩 i가 A와 B의 사이에 있는 경우에
			// (x1, y1) ~ (x2, y2)를 잇는 선이 i 지점에서의 높이
			double j = (double)((double)((y2 - y1) / (x2 - x1)) * (double)(i - x1)) + (double)y1;
			if (j <= (double) (height.at(i))) { // 선의 위치가 height보다 크면
				// 겹치는 빌딩이 있는 경우
				return true;
			}
		}
	}
	return false; // 겹치는 빌딩이 아무것도 없는 경우
}


int main() {
	int n; cin >> n; // 빌딩 개수
	height.assign(n + 1, 0); // n+1의 원소를 0의 값으로 할당

	for (int i = 1; i <= n; i++) { // i번째 빌딩
		int h; cin >> h;
		height.at(i) = h; // i번 빌딩의 높이 저장
	}

	vector<int> buildings (n+1, 0); // 각 빌딩에서 볼 수 있는 빌딩의 개수
	for (int i = 1; i <= n; i++) { // 빌딩 A
		int cnt = 0; 
		for (int j = 1; j <= n; j++) { // 빌딩 B
			if (i == j)
				continue; // 자신의 건물을 볼 수 없음.
			// A가 B를 볼 수 있는 경우
			if (!isOverlap(i, height.at(i), j, height.at(j))) {
				cnt++; // A가 볼 수 있는 빌딩 한 개 추가
			}
		}
		buildings.at(i) = cnt;
	}


	//for (int i = 0; i < buildings.size(); i++) {
	//	cout << buildings.at(i) << " ";
	//}
	//cout << endl;
	

	int max = buildings.at(1);
	for (int i = 2; i < buildings.size(); i++) {
		if (max < buildings.at(i)) {
			max = buildings.at(i);
		}
	}
	cout << max << endl;

	return 0;
}