글 읽기 - 제가 어떤 부분을 놓쳤을까요?

choyj0920 3년 전 0

선분교차2에서 맞은 코드를 가지고 좌표를 구하는 부분을 추가했는데 틀리는 이유를 잘 모르겠네요

반례 부탁 드립니다.

# baek20149 선분교차3
import sys
input=sys.stdin.readline

sys.setrecursionlimit(10**9)

d1=list(map(int,input().split()))
d2=list(map(int,input().split()))

def ccw(x1,y1,x2,y2,x3,y3):         # 외적 삼각형 넓이
    temp =x1*y2+x2*y3+x3*y1 +(-y1*x2 - y2*x3-y3*x1)

    if temp<0:      # 시계
        return -1
    elif temp==0:   # 일직선
        return 0 
    else:           # 반시계
        return 1


a=[d1[0],d1[1]]
b=[d1[2],d1[3]]
c=[d2[0],d2[1]]
d=[d2[2],d2[3]]

abc=ccw(*a,*b,*c)
abd=ccw(*a,*b,*d)
cda=ccw(*c,*d,*a)
cdb=ccw(*c,*d,*b)

if abc*abd ==0 and cda*cdb == 0:        # 선분이 평행 할 때
    if a>b: a,b=b,a                     
    if c>d: c,d=d,c
    if a==d and c<b:
        print(1)
        print(*a)
    elif a<d and c==b:
        print(1)
        print(*c)
    elif a<=d and c<=b:
        print(1)
    else:
        print(0)

elif abc*abd <=0 and cda*cdb <= 0:  # 선분이 평행하지 않을 때
    _A=b[1]-a[1]            # L1 _Ax + _By = _E
    _B=a[0]-b[0]
    _E=(_A*a[0])+(_B*a[1])
    _C=d[1]-c[1]            # L2 _Cx + _Dy = _F
    _D=c[0]-d[0]
    _F=(_C*c[0])+(_D*c[1])
    _DE=(_A*_D)-(_B*_C)
    print(1)
    if _DE != 0:
        print(((_E*_D)-(_B*_F))/_DE,end=' ')
        print(((_A*_F)-(_E*_C))/_DE)
else:
    print(0)
    


        

klm03025 3년 전 4

CCW의 곱으로 평행성을 따졌는데, 이런 경우엔 다음과 같은 케이스를 걸러내지 못합니다.

1 6 5 5
5 5 1 1

A와 B, C가 구성하는 CCW 값은 0이지만, A와 B, D가 구성하는 CCW 값은 0이 아닙니다.

당연히 C와 D, A가 구성하는 CCW는 0이 아니겠지만, C와 D, B가 구성하는 CCW는 0이겠죠.

이렇게 되면 31번째 줄로 들어가게 됩니다. 교점 여부 판단에는 문제가 없지만, 내부 조건문에 34번째에도, 37번째도 속하지 않기 때문에 교점을 출력하지 않고 프로그램이 종료될겁니다.

31번째 조건 내부에 CCW의 곱이 아닌 각각의 CCW를 다시 한 번 확인하는 조건을 내부에 삽입하면 해결할 수 있을겁니다.

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

문제

문제

출처

ICPC

제가 어떤 부분을 놓쳤을까요?

choyj0920 3년 전 0

klm03025 3년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말