취미로 코딩하기

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

이번에 볼 문제는 백준 25989번 문제인 Jabbing Jets이다.
문제는 아래 링크를 확인하자.

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

두 구멍 사이의 거리는 직선 거리를 의미하지 원의 둘레를 따라가는 거리를 의미하는 것이 아님에 유의하자.

주어지는 동심원의 반지름들의 차는 $e$보다 크므로, 하나의 원 위에 점들 사이의 거리가 $e$ 이상이 되게끔 최대한 많은 구멍을 뚫는 것으로 문제의 답을 구할 수 있음을 알 수 있다. 구멍의 개수가 증가하면 점들 사이의 거리는 점점 감소하는 관계를 이용해 이분탐색으로 답을 구하자.

이분탐색 과정에서 계산하게 되는 값은 대부분 실수인데, 실수의 경우 어느 정도 오차가 있어도 답이 제대로 계산되게끔 데이터가 주어진다고 지문에 주어져 있으므로 정확히 떨어지는 계산을 할 수 있는 유리수케이스만 특별히 신경써 문제를 해결하자. 반지름이 유리수인 원 둘레를 $n$등분하는 점들에 대하여 인접한 점끼리의 거리가 모두 유리수가 되게끔 하는 $n$은 1, 2, 6이 전부이다. (Niven's Theorem)

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

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

const ld PI = acosl(-1);
int N, E;
ll ans;

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

	cout << fixed;
	cout.precision(10);

	cin >> N >> E;
	while (N--) {
		ll r; cin >> r;
		if (r * 2 < E) {
			ans += 1;
			continue;
		}
		else if (r * 2 == E) {
			ans += 2;
			continue;
		}
		else if (r == E) {
			ans += 6;
			continue;
		}
		ll L = 1, R = 800000000;
		while (L < R) {
			ll mid = (L + R) / 2 + 1;
			ld A = PI * 2 / mid;
			ld x = ((ld)1 - cosl(A)) * 2 * r * r;
			if (x < E * E) R = mid - 1;
			else L = mid;
		}
		ans += L;
	}
	cout << ans;
}