goodinet   2년 전

안녕하세요. 10255번 교차점 문제입니다.

코드는 길지만 메인 부분을 제외하고는 '알고리즘 문제 해결 전략 1'에서 제시된 코드를 그대로 옮겨온 코드입니다!

접근 방법은 다음과 같습니다.

직사각형의 네 점을 연결되어 있는 순서대로 a,b,c,d로, 선분의 양 끝 점을 x,y로 저장합니다.

(선분 ab, 선분 bc, 선분 cd, 선분 da)와 선분 xy이 만날 경우 ans에 +1이 추가됩니다.

이 때 점 a,b,c,d에서 선분 xy와 만날 경우 한 번 만남에도 불구하고 답이 2번 추가 될 수 있는데,

모든 a,b,c,d에 대하여 각 점이 선분 x,y위에 있을 경우 ans를 하나 빼주어 올바른 답을 출력하도록 합니다.

이 때 처리하지 않은 부분은 교점이 무한히 많은 경우로서 이는

매 테스트케이스마다 chk변수를 false로 초기화 해주는데

83번째 줄에서 볼 수 있듯이 평행한 두 선분이 만날 때, 양 끝에서 만나지 않으면

이 때는 교점이 무한히 많으므로 4를 출력하도록 합니다.

여러 풀이를 찾아보았고 접근 방법이 맞는 것 같으나 어느 부분에서 틀렸는 지 잘 모르겠습니다.

랜덤 데이터와 큰 수를 넣어봐도 틀린 예제를 찾지 못하였고

여러 입력에 대해 런타임에러를 발생해보아도 데이터 상에도 문제가 없어보이는데

대체 어떤 입력에 대해서 예외가 발생하는 지 모르겠습니다.

도움 주시면 감사하겠습니다!

rhs0266   2년 전

의심가는 부분은 ccw 함수가 double 형을 return하는데 0 이라는 자연수와 비교하는 부분입니다(line 119~122).

double형이기 때문에 생기는 오차 이슈를 확인해보시거나, 입력이 전부 정수로 이뤄지기 때문에 ccw함수를 int 형으로 변형해보세요.

goodinet   2년 전

ccw함수를 int형으로 바꾸고 몇몇 함수들을 이와 맞게 수정하니 맞았습니다! 감사합니다!

예외를 찾아보고 싶지만 힘들군요ㅠ

rhs0266   2년 전

double 형의 오차를 의도적으로 발생시키는 좋은 방법은 값을 크게 키우는 것입니다. 유효숫자가 많아질수록 오차 발생이 잦아집니다.

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