호지

역시 알고리즘은 끝이없다 두 선분이 만나는지 여부는 CCW알고리즘을 통해 구할 수 있다 CCW알고리즘은 3점의 방향성을 나타내고 시계방향일때는 -1, 직선일때는 0, 반시계방향일때는 1을 반환한다. 이 방향성을 응용하여 선분이 만나는지 확인할 수 있는데, 선분1 a(x1, y1), b(x2, y2) 선분2 c(x3, y3), d(x4, y4) 이 주어졌을 때 선분ab와 점 c, 선분 ab와 점 d의 ccw값이 둘 다 -1이거나 둘 다 1이면 선분 ab와 선분 cd는 만나지 않는다. 위를 이용해 ccw를 값을 이용해 선분ab, 선분 cd에 대해 교점이 있는지 확인하는 check 함수를 구현했다. 각 점에 대한 ccw값인 abc, abd, cda, cdb를 구하고, if(abc*abd ==0 && cda*c..