onaeonae1   1년 전

CCW로 두 선분의 교차를 확인하는 문제라고 파악하고 접근했는데, 채점과 동시에 틀렸습니다가 뜹니다.

아래에 있는 코드는 CCW로 교차를 확인하는 다른 문제(https://acmicpc.net/problem/12781)에서는 문제 없이 작동했었습니다.

혹시 이 문제에서의 예외 사항이나 반례가 있어서 그런 것 같은데, 그 반례를 못찾겠습니다.

exponential_e   1년 전

오버플로우 체크해보시면 좋을 것 같네요.

(https://www.acmicpc.net/board/view/40304)

onaeonae1   1년 전

위의 링크를 읽고 crossP끼리의 곱셈에서 문제가 있는 것 같아 다음과 같이 수정하였는데, 여전히 바로 채점 시작과 동시에 틀리네요

어떤 부분에서 문제가 있는지 전혀 모르겠습니다.

exponential_e   1년 전

19번째줄에서 cp1 < 0 && cp2 < 0인 경우도 포함 되는것 아닌가요?

((cp1 < 0 && cp2 > 0) || (cp1 > 0 && cp2 <0)) && ((cp3 < 0 && cp4 > 0) || (cp3 > 0 && cp4 <0))

이게 맞는 표현 아닌가 싶습니다..

저는 ccw 문제를 풀면  실수가 잦아서.. 잘하는 편은 아닙니다만 일반적으로 저는 작성자님 처럼 crossP같은 함수를 짜고, 거기서 양수면 1 음수면 -1 아니면 0을 반환해서 쓰곤합니다.

exponential_e   1년 전

아 마지막 말은 참고하시면 좀 더 편하게 짜실 수 있지 않을까 해서 말씀드립니다!

onaeonae1   1년 전

말씀하신 대로 crossP 에서 양, 음, 0 만 리턴하도록 바꿔서 일단 오버플로우 문제를 피했습니다.

그리고 반례를 하나 찾아서 해결했습니다.

감사합니다.

exponential_e   1년 전

아 반례가 있었나요? 위에 말씀드린대로 조건문 고쳐서 작성자님 코드 그대로 붙여보니 통과하던데.. 이상하네요.

어쨌든 해결하셨다니 다행입니다.

onaeonae1   1년 전

이문제 외에도 17387도 같이 풀고 있었는데, 거기에서의 반례였네요. 거기에서 통과한 코드를 17386번 문제에 돌렸더니 통과해서 여기에도 그 반례가 적용되나 착각했던 것 같네요.

iron1209   1년 전

12781 문제는 볼록 다각형이라는 모양이 정해져 있어서 하나의 선분만을 기준으로 나머지 선분의 시작과 끝점을 비교만 하면 되지만, 이 문제는 모양이 정해져 있지 않으므로 2개의 선분 다를 기준으로 모두 해야됩니다. 휴가 11/22일부터

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