카테고리 없음

[백준/파이썬][Bronze I] Buffon's Needle - 20575

난쟁이 개발자 2025. 1. 23. 16:26
반응형

[Bronze I] Buffon's Needle - 20575

문제 링크

성능 요약

메모리: 111328 KB, 시간: 144 ms

분류

사칙연산, 수학, 문자열

제출 일자

2025년 1월 23일 16:23:48

문제 설명

For millenia, people have been interested in approximating π. One famous method is known as Buffon's Needle: drop a bunch of needles of length 1 on a coordiate plane with a vertical line drawn at each integer x coordinate (so there are lines x=0, x=1, x=−1, and so on). Each needle either intersects a vertical line, or lies entirely between two vertical lines. It turns out that, if the needles are dropped randomly, the fraction of needles that intersect a vertical line can be used to approximate π! (The specific assumptions about exactly how the needles are dropped in the experiment are not important for this problem.)

In particular, let x be the fraction of needles that intersect a vertical line. Then

 π≈2x. 

You are given the positions of N needles (not necessarily random), and it is guaranteed that at least one of them intersects a vertical line. What is the corresponding approximation of π, using the above formula?

입력

The first line of input contains a single integer N (1≤N≤104), the number of needles. N lines follow.

The i-th such line describes the i-th needle. It contains four real numbers: xi1,yi1,xi2,yi2. This means that the i-th needle has one endpoint at (xi1,yi1) in the plane and the other endpoint at (xi2,yi2).

All real numbers in the input are given with exactly 6 digits after the decimal point and have absolute value at most 10. Furthermore, it is guaranteed that no x coordinates in the input are within 10−6 of an integer.

Since all the needles are of length 1, for each i it is guaranteed that

 |(xi1−xi2)2+(yi1−yi2)2−1|<10−3. 

출력

Output a single real number, the approximation of π described above. Your answer is considered correct if its absolute or relative error is at most 10−6.

풀이

def trunc(x) :
    if x >= 0 :
        return int(x)
    else :
        return -int(abs(x) + 1)

def main() :
    # the number of needles
    N = int(input())

    cnt = 0
    for _ in range(N) :
        # 바늘의 시작점과 끝점 좌표
        x1, y1, x2, y2 = map(float, input().split())

        # 버리기
        x1_trunc = trunc(x1)
        x2_trunc = trunc(x2)

        frac = abs(x1_trunc - x2_trunc)
        if frac >= 1 :
            cnt += 1

    X = cnt / N
    pi = 2 / X

    print(f'{pi:.6f}')

    # pi = 2 / X => pi 를 구하는 ...
    # 실수를 구하는 문제
    # x의 수직선에 걸리는? 바늘의 개수를 찾는 그런 문제인 것 같다.
    # 그럼 y 는 필요가 없네?
    # x1 - x2 가 정수이기만 하면 이 문제는 풀리는거 아닌가?
    # 아 그게 아니라 그냥 x가 정수인 부분만 넘기는 바늘 갯수만 세면 되네
    # 그럼 그냥 1.999999 => 2.000001 도 x=2 에 걸쳐지는 거니까
    # 소수점 이하는 버리고 차이의 절대값이 0 보다 크기만 하면 된다.
    # 그냥 int 로 취하니까 오류가 난다.
    # 음수가 있어서? 그런걸까?

변수 중간에 바꾼걸 깜빡하고 계속 틀려서 헤맸던 문제이다.

그냥 int 로 취하게 되면 음수 부분에서 오류가 있을거 같아서 trunc 함수를 만들어서 음수 부분에서 -1 을 더 이동하게 만들었고, 절대값으로 차이를 구했을 때, 1 이상의 차이가 보이면 => x 수직선에 걸쳐졌다고 판단. 0 > 이 아니라 정확하게는 1>= 이어야 하는디 문제에선 그냥 통과 되네요 허허... 이런 오류는 조심합시다.

위는 수정한 코드, 아래는 수정 전 코드 이다. 수학적으로는 아마 위의 코드가 더 정확한 코드일 거라고 생각한다. 화이팅!

def trunc(x) :
    if x >= 0 :
        return int(x)
    else :
        return -int(abs(x) + 1)

def main() :
    # the number of needles
    N = int(input())

    cnt = 0
    for _ in range(N) :
        # 바늘의 시작점과 끝점 좌표
        x1, y1, x2, y2 = map(float, input().split())

        # 버리기
        x1_trunc = trunc(x1)
        x2_trunc = trunc(x2)

        frac = abs(x1_trunc - x2_trunc)
        if frac > 0 :
            cnt += 1

    X = cnt / N
    pi = 2 / X

    print(f'{pi:.6f}')

    # pi = 2 / X => pi 를 구하는 ...
    # 실수를 구하는 문제
    # x의 수직선에 걸리는? 바늘의 개수를 찾는 그런 문제인 것 같다.
    # 그럼 y 는 필요가 없네?
    # x1 - x2 가 정수이기만 하면 이 문제는 풀리는거 아닌가?
    # 아 그게 아니라 그냥 x가 정수인 부분만 넘기는 바늘 갯수만 세면 되네
    # 그럼 그냥 1.999999 => 2.000001 도 x=2 에 걸쳐지는 거니까
    # 소수점 이하는 버리고 차이의 절대값이 0 보다 크기만 하면 된다.
    # 그냥 int 로 취하니까 오류가 난다.
    # 음수가 있어서? 그런걸까?
main()

 

반응형