만약 의도된 알고리즘을 구현했고 반례를 못 찾겠다면 오버플로우 문제일 가능성이 큰 것 같습니다.
저같은 경우는 정수 연산만 사용해서 교점을 구했는데, 이럴 경우 a/b (<, =, >) c/d꼴의 분수 비교가 필요하기 때문에 양변에 bd를 곱해서 ad와 bc를 비교하니 (64비트 정수)*(64비트 정수)꼴의 연산이 나오게 됩니다. 당연히 대충 64비트로 선언해주면 될 줄 알았는데, long long으로도 오버플로우가 뜰 줄은 상상도 못 했습니다...
저는 __int128_t를 사용해서 해결했지만 double로도 되는 것을 확인했습니다. long long으로도 안 되는 문제는 백준에서 처음 본 것 같네요
hyper1423 1년 전
만약 의도된 알고리즘을 구현했고 반례를 못 찾겠다면 오버플로우 문제일 가능성이 큰 것 같습니다.
저같은 경우는 정수 연산만 사용해서 교점을 구했는데, 이럴 경우 a/b (<, =, >) c/d꼴의 분수 비교가 필요하기 때문에 양변에 bd를 곱해서 ad와 bc를 비교하니 (64비트 정수)*(64비트 정수)꼴의 연산이 나오게 됩니다. 당연히 대충 64비트로 선언해주면 될 줄 알았는데, long long으로도 오버플로우가 뜰 줄은 상상도 못 했습니다...
저는 __int128_t를 사용해서 해결했지만 double로도 되는 것을 확인했습니다. long long으로도 안 되는 문제는 백준에서 처음 본 것 같네요