일어나!
시간 제한1초메모리 제한128 MB
최대 2만 개의 선분들이 서로 교차하는 서로 다른 교점의 개수를 효율적인 기하 알고리즘으로 구하는 문제입니다.
문제
깨어나세요, 용사여!
이 세계를 지키는 N명의 용사가 각자 하나의 선분 위를 빛처럼 빠르게 계속 왕복한다. 두 용사가 같은 위치에서 만나면 서로 부딪혀 깨어난다.
각 용사가 움직이는 선분들이 주어질 때, 두 용사가 부딪힐 수 있는 서로 다른 위치의 개수를 구하라.
세 용사가 한 위치에서 동시에 만나거나, 두 용사가 같은 선분 구간을 함께 움직이는 경우는 주어지지 않는다.
입력
첫째 줄에 용사의 수 N이 주어진다. (0 <= N <= 20,000)
다음 N개의 줄에는 각 용사가 움직이는 선분의 두 끝점 (x1, y1)과 (x2, y2)가 주어진다. (-1,000,000 <= x1, y1, x2, y2 <= 1,000,000)
출력
용사들이 부딪힐 수 있는 서로 다른 지점의 개수를 출력한다.
정답은 100,000 이하이다.