[백준 20575] Buffon’s Needle (C#, C++) - soo:bak

문제 링크

20575번 - Buffon’s Needle

설명

길이 1인 바늘 N개가 주어집니다. 세로 격자선은 모든 정수 x에 있고, 바늘이 어떤 세로선이라도 교차하면 교차로 셉니다.

교차한 바늘의 비율을 이용하여 원주율을 근사하는 문제입니다. 교차한 개수를 구한 뒤 2 곱하기 N을 교차한 개수로 나누면 됩니다.

접근법

먼저, 바늘의 양 끝점 x 좌표가 주어집니다. 바늘 길이가 1이므로 x 좌표 차이는 1 이하이며, 교차 가능한 세로선은 최대 하나입니다.

다음으로, 두 끝점의 x 좌표를 각각 내림한 값이 서로 다르면 그 사이에 정수 세로선이 있으므로 교차한 것입니다. 끝점이 정수선 위에 정확히 놓이는 경우는 없다고 보장됩니다.

이후, 모든 바늘에 대해 교차 여부를 판정하고 교차한 개수를 셉니다. 마지막에 2 곱하기 N을 교차한 개수로 나눈 값을 출력합니다.

---

Code

C#

using System;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var n = int.Parse(Console.ReadLine()!);
      var hit = 0;
      for (var i = 0; i < n; i++) {
        var p = Console.ReadLine()!.Split();
        var x1 = double.Parse(p[0]);
        var x2 = double.Parse(p[2]);

        var f1 = (long)Math.Floor(x1);
        var f2 = (long)Math.Floor(x2);
        if (f1 != f2)
          hit++;
      }

      var pi = 2.0 * n / hit;
      Console.WriteLine(pi.ToString("0.000000"));
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

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

  int n; cin >> n;
  int hit = 0;
  for (int i = 0; i < n; i++) {
    double x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    ll f1 = floor(x1);
    ll f2 = floor(x2);
    if (f1 != f2)
      hit++;
  }

  cout << fixed << setprecision(6) << 2.0 * n / hit << "\n";

  return 0;
}