기하학 (2) 계산 문제들

1207번 고층건물 - 기울기

16190번 Rising Sun - 좌표, 기울기

16115번 팬이에요 - 삼각함수

1798번 원뿔좌표계상의 거리 - 좌표, 삼각함수

---

1207번 고층 건물

같은 간격으로 떨어져 있는 건물의 높이가 정수로 주어질 때

각 건물의 옥상에서 보이는 다른 건물의 개수 중 최댓값 출력

현재 건물과 보려고 하는 건물의 옥상을 이은 선분에 다른 건물이 교차하거나 만나면 안 된다.

 

즉, 현재 건물의 옥상을 점 A라 하고

현재 건물에서 볼 수 있는 건물의 옥상을 왼쪽에서 오른쪽 순서로 각각 점 B1, B2, ...라 하면

선분 AB1, AB2, ...의 기울기가 순서대로 증가해야 함

 

 

 

기울기가 같으면 안 됨. 8에서는 7만 보이고 6은 볼 수 없다.

 

 

높이가 극댓값인 건물만 보면 틀린다.

낮은 건물에서 다른 건물이 더 많이 보일 때가 있다.

걍 다 찾아야 되는 것이다.

 

 

 

 

코드

 

h[N] 각 건물의 높이

s[N][N] s[i][j]=i, j번째 건물 간 기울기

 

i번째 건물에서 보이는 건물의 수를 구할 때

line 20: 바로 옆 건물은 무조건 보임. 양 끝 건물은 +1, 그 사이는 +2

line 22-30: 바로 옆 건물과의 기울기를 기준으로 왼쪽, 오른쪽으로 보이는 건물의 수 계산

#include <cstdio>
using namespace std;

double s[52][52];
int main() {
	int N, h[51];

	scanf("%d", &N);
	for (int i = 1; i <= N; ++i) scanf("%d", &h[i]);
	if (N < 3) { printf("%d", N - 1); return 0; }

	for (int i = 1; i < N; ++i) {
		for (int j = i + 1; j <= N; ++j)
			s[i][j] = s[j][i] = ((double)(h[j] - h[i])) / ((double)(j - i));
	}

	int CNT = 0, TMP;
	double right, left;
	for (int i = 1; i <= N; ++i) {
		TMP = (i == 1 || i == N) ? 1 : 2;

		left = s[i][i - 1];
		for (int j = i - 2; j > 0; --j) {
			if (s[i][j] < left) TMP++, left = s[i][j];
		}

		right = s[i][i + 1];
		for (int j = i + 2; j <= N; ++j) {
			if (s[i][j] > right) TMP++, right = s[i][j];
		}
		if (CNT < TMP) CNT = TMP;
	}
	if (CNT < TMP) CNT = TMP;

	printf("%d", CNT); return 0;
}

 

 

---

16190 Rising Sun

좌표 상 기울기가 1, -1인 선분으로 이루어진 산과 산 위의 집이 있다.

산은 (a0,0)에서 오르막으로 시작,

기울기가 바뀔 때의 x좌표가 오름차순으로 a1, a2, .. a2n-1로 주어지고

마지막에는 집이 존재하는 x좌표 x0∈[a0, a2n-1] 가 주어진다.

 

해는 원점에서 1분에 1씩 위로 움직인다.

해를 볼 수 있는 가장 짧은 시간을 정수로 출력

고층 건물 문제와는 다르게 해와 산꼭대기와 집이 일직선 상에 있어도 해를 볼 수 있다.

 

example

 

 

 

 

세 가지 경우로 생각

 

 

① a0 ≤ x0 ≤ a1: 0 출력

 

② 오르막: 집의 왼쪽에 있는 극대점과 집을 이은 직선의 y좌표가 가장 클 때. y좌표가 음수이면 0

 

③ 내리막: 해와 집을 이은 직선의 기울기가 -1일 때

 

 

좌표, y절편, 직선의 방정식 등 계산에 주의한다.

 

 

 

코드

 

a[2N] a0 a1 a2 ... 을 저장

b[N] 극대점일 때의 높이 저장. 산의 극대점은 (a[k],b[k/2]), k=odd

x0,y0 집의 위치 

 

line 16: ①

line 27-42: ②

line 46: ceil 주의

line 43-50: ③

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
//a 0 1 2 3 4 ... 2n-2 2n-1
//b   0   1   ......    n-1
//  ↗↘↗↘        ↗↘
// [0,1](1,2]....(2n-2,2n-1]

int main() {
	int N, a[2000], b[1000];
	int x0, y0;
	scanf("%d", &N);
	for (int i = 0; i < 2 * N; ++i) scanf("%d", &a[i]);
	scanf("%d", &x0);
	if (x0 <= a[1]) { printf("0"); return 0; }

	// Calculate 극대점
	b[0] = a[1] - a[0];
	for (int i = 1, j = 1; i < N; ++i, j += 2)
		b[i] = b[i - 1] + a[j] - 2 * a[j + 1] + a[j + 2];

	// Find where is the house & ANS
	int ANS;
	auto k = lower_bound(a, a + 2 * N, x0) - a;

	if (k % 2) {
		//if 오르막
		//내 앞의 극대점이랑 이은 직선의 y절편 가장 클 때
		//For all a[i],b[i/2], i=odd
		//y=(y0-b / x0-a)*(x-x0)

		y0 = x0 - a[k] + b[k / 2];

		double sun = -987654321;
		for (int i = 1; i < k; i += 2) {
			double m0 = ((double)(y0 - b[i / 2]) / (double)(x0 - a[i]));
			double tmp = ceil(-m0 * (double)x0 + y0);
			if (sun < tmp) sun = tmp;
		}
		ANS = (sun < 0) ? 0 : ((int)sun);
	}
	else {
		//if 내리막
		//기울기가 -1이고 (x0,y0)을 지나야 함
		//y=-(x-x0)+y0
		//Here, y0 = -x0 + a[k] + b[k / 2]

		k--; ANS = a[k] + b[k / 2];
	}
	printf("%d", ANS); return 0;
}

 

 

---

16115번 팬이에요

원점을 포함하는 다각형의 각 꼭짓점이 시계 반대방향 순으로 주어질 때

원점을 기준으로 다각형을 회전시켜 원을 만들 수 있는 최소 각을 도(°) 단위로 구하는 문제

원점에서 각 꼭짓점을 이은 선분은 모두 다각형의 내부에 온전히 존재한다.

 

STEP 1. 원의 반지름을 결정하는 꼭짓점 벡터에 저장

원의 반지름 = 원점에서 가장 먼 꼭짓점까지의 거리

 

STEP 2. 각 꼭짓점과 원점을 이은 동경의 각, 이웃한 각 간의 차 계산

atan2(y,x) = 점(x,y)와 원점을 이은 동경의 각(radian)

이때 -π < atan2(y,x) ≤ π 이므로 각의 차이가 음수이거나 0이면 +2π

 

 

 

 

 

코드

 

R 원의 반지름

v 원주 위에 존재하는 꼭짓점을 저장

fir 가장 처음으로 주어진 꼭짓점에 대한 각

 

line 13: 굳이 sqrt계산 안 해도 됨

line 28, 31: <=

 

#include <cstdio>
#include <math.h>
#include <vector>
using namespace std;

vector<pair<double, double>> v;
int main() {
	double R = 0, a, b;
	int N;
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) {
		scanf("%lf%lf", &a, &b);
		double r = a * a + b * b;

		if (r > R) v.clear(), v.push_back({ a,b }), R = r;
		else if (r == R) v.push_back({ a,b });
	}

	double ANS = 0, TMP;
	double fir = atan2(v[0].second, v[0].first) * 180 / 3.1415926535;

	double A = fir, B;
	for (int i = 1; i < v.size(); ++i) {
		B = atan2(v[i].second, v[i].first) * 180 / 3.1415926535;

		TMP = B - A + ((B <= A) ? 360 : 0);
		A = B;
		if (ANS < TMP) ANS = TMP;
	}
	TMP = fir - A + ((fir <= A) ? 360 : 0);
	if (ANS < TMP) ANS = TMP;

	printf("%.7f", ANS); return 0;
}

 

 

---

1798번 원뿔좌표계상의 거리

설명은 필기로 대체한다.. 고등수학이니깐

 

 

 

코드

 

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cout << fixed;
	cout.precision(2);

	double r, h, d1, A1, d2, A2, alpha, ANS;
	while (cin >> r >> h >> d1 >> A1 >> d2 >> A2) {
		alpha = 3.14159265 * r * min(abs(A2 - A1), abs(A1 + 360 - A2)) / (180.0 * sqrt(r * r + h * h));
		ANS = sqrt(d1 * d1 + d2 * d2 - 2.0 * d1 * d2 * cos(alpha));

		cout << (round(ANS * 100.0) / 100.0) << "\n";
	}
	return 0;
}

입력의 수가 주어지지 않은 케이스,,,

그 덕에 cout으로 소수점 출력하는 법을 찾아보았다.