취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 26654번 문제인 원점이다.
문제는 아래 링크를 확인하자.

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

정다각형의 각 꼭짓점 또한 원 하나의 원주(원의 둘레) 위에 전부 올릴 수 있음을 생각하면 문제를 쉽게 접근할 수 있다.

정다각형의 외접원의 반지름보다 반지름이 큰 원은 정다각형의 모든 꼭짓점을 포함할 수 있다. 그렇지 않을 경우 원은 정다각형의 외접원의 원주의 절반 이상을 덮을 수 없으므로 많아야 \(N/2\)개의 꼭짓점만을 포함할 수 있다.

정다각형의 외접원의 반지름을 먼저 계산하고(사인 법칙 등 구할 방법은 많으니 편한 방법을 선택하자), 위의 관찰을 이용해 몇 개의 꼭짓점을 포함할 수 있는지 이분탐색을 이용해 구해 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <cmath>
using namespace std;
typedef long double ld;

const ld PI = acosl(-1);
int N, A, B;
ld R1, R2, theta;
ld X, Y;

void solve() {
	cin >> N >> A >> B;
	theta = PI * 2 / N;
	R1 = sqrtl((ld)A * 2 / (N * sinl(theta)));
	R2 = sqrtl((ld)B / PI);

	if (R1 <= R2) {
		cout << N << '\n';
		return;
	}

	X = cosl(theta), Y = sinl(theta);
	if (hypotl(1 - X, Y) * R1 > R2 * 2) {
		cout << 1 << '\n';
		return;
	}
	int L = 1, R = N / 2;
	while (L < R) {
		int mid = (L + R) / 2 + 1;
		X = cosl(theta * mid), Y = sinl(theta * mid);
		if (hypotl(1 - X, Y) * R1 > R2 * 2) {
			R = mid - 1;
		}
		else L = mid;
	}
	cout << L + 1 << '\n';
}

int T;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> T;
	while (T--) solve();
}

BOJ Random Defense #17