Logo
(追記) (追記ここまで)

오차를 줄이려면 어떻게 해야 하나요?

1046번 - 그림자

특정 각도로 발사한 광선이 벽에 부딪히는 좌표를 구하고 그 광선에 대해 작은 각도만큼 회전한 광선이 벽에 부딪히는 좌표를 구한 뒤 광원과 두 충돌 지점이 이루는 삼각형의 넓이를 구분구적법을 이용해 더해가는 방식으로 풀이하였습니다. 그런데 이 방법으로 오차를 10-9 이내로 줄이는 법을 모르겠습니다. 오차를 줄이기 위해 각도를 더 잘게 쪼개면 제한 시간 내에 답을 구할 수 없을 것 같습니다. 오차를 줄이기 위해서는 혹시 이 방법이 아닌 다른 방법을 사용해야 하나요?

1. 설명으로는 360/piece° 단위로 직접 돌려가며 광원, 교점1, 교점2로 이루어지는 삼각형의 넓이를 더하는 것으로 보이는데 실제로 사각형이 구성되나 삼각형으로 처리하면서 생기는 오차와 자잘한 실수연산이 누적되면서 쌓이는 오차가 작지는 않을 것으로 보입니다. 고정각만큼 돌리는 것보다는 확인해야 하는 각의 후보를 격자점을 기준으로 잡아주는 것도 좋을 것 같습니다. 빛이 닿는 벽이 바뀌는 경계는 결국 광원->벽의 끄트머리 (격자점)을 지나는 케이스기 때문에 코드에 제시된 piece의 값보다 더 작은 각의 경우만 탐색할 것이고 사각형도 나오진 않으니 오차는 줄어들 것 같습니다. (이 부분은 제가 직접 구현해보진 않아서 확답 하진 못하겠습니다.)

2. 다른 방법으로는 미세하게 각을 돌리면 충돌하는 점들이 똑같은 한 선분(벽의 한쪽 면) 위에 있는 중복된 경우가 많은데 이걸 여러 번 안 쪼개고 한 번에 묶어서 처리할 방법을 고민해보시면 좋을 것 같습니다. 다르게 말하면 쪼개지는 무수하게 많은 작은 삼각형들을 잘 묶어보면 큰 삼각형 몇 개로 모아서 처리할 수 있습니다.

댓글을 작성하려면 로그인해야 합니다.

(追記) (追記ここまで)

출처

대학교 대회

  • 사업자 등록 번호: 541-88-00682
  • 대표자명: 최백준
  • 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
  • 전화번호: 02-521-0487 (이메일로 연락 주세요)
  • 이메일: contacts@startlink.io
  • 통신판매신고번호: 제 2017-서울서초-2193 호

AltStyle によって変換されたページ (->オリジナル) /