kcm1700   1년 전

이 지적은 Pasture 시리즈 문제 열 개에 모두 적용해야 할 내용입니다.

길이를 정확하게 계산하여 더한 경우 다음과 같은 길이가 나옵니다.

19997 35358880.707461

하지만 체커는 다음의 틀린 값만 정답으로 인정합니다.

19997 35358880.707452

공식 체커는 부동소수점을 제대로 다룰 줄 모르고 엉터리로 거리를 계산해서 더합니다. 애초에 체커에서 계산한 길이의 합은 오차가 크기 때문에 그것과 비교하는 것은 틀렸습니다.

코드의 다음 부분을 여유를 많이 준 상대오차 체크로 변경해주세요. 1e-6 정도의 절대/상대오차 비교가 좋아보입니다. 현재 절대오차 1e-6는 틀린 값으로 계산하길 요구하는 것이 됩니다.

if(abs(pikk-d)>=0.000001) lopeta(0,"Invalid length");

구체적으로는 teetraat()와 kaug() 구현이 틀렸습니다. pikk라는 double 변수에 아무 생각 없이 kaug()를 더하는데, 심지어 kaug()는 hypot()을 쓴 것도 아니고 sqrt(a*a+b*b)라 더욱 오차가 큽니다. 엉성하게 오차 범위 따져보면 kaug 한번에 1e-8까지 상대오차가 생길 수 있고, 이것을 수만번 더하기 때문에 더욱 오차가 큽니다. (수정: kaug() 부분은 문제 좌표 범위 제한 덕분에 오차 문제는 특별히 크지 않습니다)

공식 체커를 나름대로 수정한 것을 첨부합니다.

corhydrae   1년 전

문제는 아직 풀어보지 않아서 잘 모르겠습니다만, checker만 보자면 kaug()에는 별다른 문제가 없어 보입니다. teetraat() 쪽이 잘못된 것 같네요.

kcm1700   1년 전

@corhydrae 첨부한 코드는 제가 수정한 겁니다.

corhydrae   1년 전

@kcm1700 아뇨, 원본 checker와 비교해 본 결과 그렇다는 말씀입니다.

kcm1700   1년 전

혹시 sqrt(a*a+b*b)가 옳다고 생각하시는 건가요? 오차가 hypot으로 하는 것보다 많이 커질 수 있어요.

아 문제 제한이 10^5이어서 문제가 안 생길 수도 있군요.

corhydrae   1년 전

옙. 실제 문제에 주어진 input 데이터를 집어넣고 비교해 본 결과입니다. double 자체의 정밀도 한계에 비해 별달리 큰 오차는 발생하지 않았습니다. kaug() 내에서 sqrt()와 hypot<double>()을 각각 사용해서 얻은 결과를 비트 단위로 비교해보시면 아실 수 있을 겁니다.

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