naegeora   5달 전

아래 로직에 따라서 작성했는데 틀렸다고 나오네요....한 4시간동안 버그잡으려고 하는데 안잡혀서...

거의 다 한것 같은데 안되서..고수님들의 고견을 부탁합니다.

1.가장작은 y좌표,x좌표 를 기준점으로 각도순으로 정렬함. [cosine값을 내림차순 정렬함]
2. 정렬된 점들을 따라가며 연속된 세점들(P[i],P[i+1],P[i+2])에 대해 ccw이면 que에 P[i+2]를 넣고, 
아니면 P[i+1]을  que에서 빼고 que에서 first/second 유지하고 P[i+2]를 다시 ccw 
3. 위과정을  N 까지 돌리고 P[0]를 넣어서 CCW를  돌려서 P[N-1]을 점검함.



ntopia   5달 전

주어진 좌표의 범위를 고려하면

ccw를 계산하다 오버플로우가 나는 것 같습니다

naegeora   5달 전

아래를 long로 바꾸었는데도 계속 틀렸다고 나네요

혹시 틀린케이스를 알수 있을까요? 예제와 제가 만들어서 테스트 해본 결과는  다 맞아서요....

public static long ccw(point p1, point p2, point p3) {
        return p1.x*p2.y+p2.x*p3.y+p3.x*p1.y-p2.x*p1.y-p3.x*p2.y-p1.x*p3.y;    
    }

ntopia   5달 전

여전히 오버플로우의 가능성이 있습니다

ntopia   5달 전

int로 40000 * 40000 + 40000 * 40000 을 계산하면 어떻게 되는지 직접 확인해보면..

naegeora   5달 전

ntopia님 상세한 설명 감사합니다.

아래 리턴값 뿐만 아니라 x,y 좌표들도 전부 long 값으로 바꾸었습니다만, 틀렸다고 나오네요....위 소스 Long로 수정했어요...

틀린케이스를 알고 싶습니다...흑흑..

물론 아시겠지만..

int 최대값 : 2147483647
long 최대값 : 9223372036854775807

public static long ccw(point p1, point p2, point p3) {        return p1.x*p2.y+p2.x*p3.y+p3.x*p1.y-p2.x*p1.y-p3.x*p2.y-p1.x*p3.y;         }

baekjoon   5달 전

자바의 long은 C++ 에서 long long 입니다

naegeora   5달 전

long 으로 바꾸어서 오버플로우 문제는 해결한것 같은데 틀려서 마음이 아주 아픕니다...

이게 해결되야 풀리는 다른문제들이 있어서....도움좀 부탁드려요..

naegeora   5달 전

아...드디어 해결했습니다...

이렇게 기쁠수가....고수님들 감사합니다...

위에서 각도정렬과 각도가 같으면 거리정렬인데...

거리정렬에서 문제가 있었네요.

return (int) (o1.distance-o2.distance);==>return (o1.distance-o2.distance>0?1:-1);

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