대나무 베기

두 끝점의 $y$좌표가 서로 반대 부호일 때만 선분의 내부가 $y=0$과 만난다. 같은 부호이면 선분 전체가 한쪽에 있고, 한쪽이 $0$이면 끝점에서만 만난다. 두 값이 모두 $0$인 입력은 없다. 따라서 반대 부호인 대나무만 세면 된다. 시간 복잡도는 $O(\sum N)$, 추가 공간은 $O(1)$이다. 단순 풀이는 $Y_{1,i}Y_{2,i}<0$을 검사해도 된다. 곱의 절댓값은 최대 $10^{12}$이므로 64비트 정수를 쓴다.

Solution written by GPT6.1