1234juwon   1년 전

testcase.ac에서도 반례 없다고 하고.. 게시판에 있는 반례들 전 부 다 넣어봤지만 다 정답대로 나오네요..

혹시 반례 있을까요?

dlwocks31   1년 전

확률이 낮아서 안나왔던 것 같네요. https://testcase.ac/submission/160723

두 점이 같을 때 문제가 생기는 듯 합니다

입력:

-76 26 -18 21
-76 26 -18 25

오답 출력:

0

정답 출력:

1

1234juwon   1년 전

앗.. 반례가 testcase.ac에 있었군요! 정말 감사드립니다

1234juwon   1년 전

그런데, 여전히 35%쯤에서 틀렸습니다 가 뜹니다. 어떻게 해야 할까요?(오차범위 설정까지 해봤습니다.)

dlwocks31   1년 전

일단 말씀드릴 것은 `getcontext().prec` 는 decimal에 대한 메소드인데 계산 자체는 float로 처리했기 때문에, `getcontext().prec` 가 현재 코드에 영향이 전혀 없습니다.

부동소수점 오차가 오류의 원인은 맞아 보이는데, 여기서는 decimal을 사용하는 것도 좋지만 더 좋은 방법은 정수만을 이용해 오차가 없는 "ccw 선분 교차" 이기 때문에 이에 대해서 검색해서 알아보시는 것을 추천드립니다.

아래는 반례입니다. (제너레이터를 새로 추가했습니다.) https://testcase.ac/submission/163855

입력:

-439 -896 753 200
8 -485 747 444

오답 출력:

0

정답 출력:

1


1234juwon   1년 전

갑사합니다! 문제는 ccw 알고리즘으로 해결했습니다. ^^

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