겹치는 선분
시간 제한2초메모리 제한256 MB
선분 최대 10만 개 중에서 한 점만 접하는 경우를 제외하고 양의 길이만큼 겹치는 선분 쌍의 개수를 구합니다.
문제
N개의 선분이 주어진다. 두 선분이 한 점이 아니라 길이가 있는 구간을 공유하면 두 선분이 겹친다고 한다. 다시 말해 두 선분에 공통으로 포함되는 점이 무한히 많아야 한다. 끝점 하나만 같은 경우는 겹치는 것으로 보지 않는다.
주어진 선분 중 서로 겹치는 서로 다른 선분 쌍의 개수를 구하라.
N은 1 이상 100,000 이하이다.
입력
첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 선분의 두 끝점 좌표 x1 y1 x2 y2가 공백으로 구분되어 주어진다.
모든 좌표는 0 이상 1,000,000 이하의 정수이며, 한 선분의 두 끝점이 같은 경우는 주어지지 않는다.
출력
첫째 줄에 서로 겹치는 서로 다른 선분 쌍의 개수를 출력한다.