풀이 이 문제는 ccw와 union find를 이용하여 해결 할 수 있다. 두 직선이 교차되었는지 판별은 선분 교차2와 동일하다. 모든 선분들에 대해 서로 교차되었는지 판변하고 교차되었다면 union을 한다. ccw의 리턴값을 1 -1 0이 아닌 원래 값으로 리턴하여, check함수에서 두 값을 곱할 시 오버플로우가 발생할 것을 예상하지 못하고 맞왜틀을 외쳤다. 조심하도록 하자. 코드 #include #include #define x first #define y second using namespace std; using pii = pair; pii a[3003], b[3003]; int par[3003], member_size[3003]; int ccw(pii a, pii b, pii c) { int ..

풀이 선분의 교차는 ccw의 값으로 구한다. ccw를 모른다면 여기를 참고하자. 직선이 교차하기 위해서는 abc abd의 ccw값의 부호가 다르고, cda cdb의 값의 부호도 달라야한다. 직선이 겹치는 경우는 항상 a b) swap(a, b); if (c > d) swap(c, d); return a