이 문제의 정해는 심슨 적분으로 각 구간의 기댓값 적분을 더하는 것입니다만 저는 그린 정리 + 스위핑으로 AC를 받았습니다(심슨 적분이 뭔지 모릅니다).
제 방법의 시간복잡도를 계산해보면 (N^2logN, N == 1000 * (2 ~ 4)) 이론적으로는 문제가 없으나 실수 자료형으로 연산하기에 현실적인 시간 제한은 아닙니다. 저는 다른 그린 정리를 활용하는 문제들을 풀어봐서 최적화를 하는 방법을 알고 있으나 정해는 훨씬 느린 심슨 적분으로도 풀 수 있어야 하기 때문에 시간 제한을 늘려야할 것으로 보입니다.
jhwest2 님의 요청글에도 나와있지만 문제 공식에서 주어진 제한 시간은 9.5초입니다. 한국 서버의 연산 속도를 고려해서 4 ~ 5초 사이로 늘려주는 것을 요청합니다.
redcube231 1년 전 1
이 문제의 정해는 심슨 적분으로 각 구간의 기댓값 적분을 더하는 것입니다만 저는 그린 정리 + 스위핑으로 AC를 받았습니다(심슨 적분이 뭔지 모릅니다).
제 방법의 시간복잡도를 계산해보면 (N^2logN, N == 1000 * (2 ~ 4)) 이론적으로는 문제가 없으나 실수 자료형으로 연산하기에 현실적인 시간 제한은 아닙니다. 저는 다른 그린 정리를 활용하는 문제들을 풀어봐서 최적화를 하는 방법을 알고 있으나 정해는 훨씬 느린 심슨 적분으로도 풀 수 있어야 하기 때문에 시간 제한을 늘려야할 것으로 보입니다.
jhwest2 님의 요청글에도 나와있지만 문제 공식에서 주어진 제한 시간은 9.5초입니다. 한국 서버의 연산 속도를 고려해서 4 ~ 5초 사이로 늘려주는 것을 요청합니다.