fork(1) download
copy 
  1. #include<iostream>
  2. #include<cmath>
  3. #include<iomanip>
  4. using namespace std;
  5. long long n, k;
  6. long double L, R, H[800000];
  7. long double SIN(long double deg) {
  8. 	return sin(3.14159265358979323846264l / 180.0l*deg);
  9. }
  10. long long HS(long double I) {
  11. 	long long L = 0, R = n, M;
  12. 	while (true) {
  13. 		M = (L + R) / 2;
  14. 		if (H[M] <= I && H[M + 1] > I)return M;
  15. 		if (M == n - 1 && H[M + 1] <= I)return n;
  16. 		if (H[M] > I)R = M;
  17. 		if (H[M + 1] <= I)L = M;
  18. 	}
  19. }
  20. long long solve(long double cnt) {
  21. 	long long ret = 0;
  22. 	for (int i = 1; i <= n - 2; i++) {
  23. 		long double I = SIN(180.0l*i / n) * 2.0l;//横幅
  24. 		long double J = cnt / I * 2.0l;//最大の高さ
  25. 		long double R = 0;
  26. 		if (i >= n / 2)R = 1.0l + sqrtl(1.0l - (I / 2.0l)*(I / 2.0l));//線の高さ
  27. 		if (i < n / 2)R = 1.0l - sqrtl(1.0l - (I / 2.0l)*(I / 2.0l));//線の高さ
  28. 		long long K = HS(J + R);//許される最大のz座標
  29. 		long long F = ((K - i) / 2) * 2;//何通りか
  30. 		if (K == n && (n - i) % 2 == 0) { F--; }
  31. 		ret += F*n * 2;
  32. 	}
  33. 	return ret;
  34. }
  35. int main() {
  36. 	cin >> n >> k;
  37. 	for (int i = 0; i <= n; i++)H[i] = SIN(360.0l*i / (n * 2) - 90.0l) + 1.0l;
  38. 	long double L = 0, R = 1.3l, M;
  39. 	for (int i = 0; i < 50; i++) {
  40. 		M = (L + R) / 2.0l;
  41. 		long long T = solve(M);
  42. 		long long U = solve(M - 1.0l*(1.0e-10));
  43. 		if (T >= k * 6 && U < k * 6) { break; }
  44. 		if (U >= k * 6) { R = M; }
  45. 		if (T < k * 6) { L = M; }
  46. 	}
  47. 	cout << fixed << setprecision(15) << M << endl;
  48. 	return 0;
  49. }
Success #stdin #stdout 0s 12848KB
comments (?)
stdin
copy 
12 220
stdout
copy 
1.299038105725776
https://ideone.com/YfmWgB
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!