2차원 평면에서 두 선분이 만나는 경우의 수

2차원 평면에서 하나의 점은 x선분과 y선분을 이용하여 표현할 수 있다.

아래 그림과 같은 경우 점 a는 (1, 0), 점 b는 (4, 3) 이라고 나타낼 수 있다.

2차원 평면에서 선분은 두 개의 점으로 표현할 수 있다.

예를 들어 위 그림에서 점 a, b를 잇는 선분은 두 점의 좌표를 잇달아 적어 (1, 0, 4, 3)라고 나타낼 수 있다.

선분 ab는 아래 그림과 같다.

선분 정보가 N개 주어질때 임의의 두 선분이 서로 만나거나 교차하는 경우의 수를 구하는 프로그램을 작성하시오.

두 선분의 끝점이 닿기만하는 경우나 포개어 지는 경우도 경우의 수에 포함된다.

아래 예를 보면 5개의 선분이 주어진 경우이다.

두 선분이 서로 만나거나 교차하는 경우를 순서쌍으로 나타내 보면

(2번 선분, 3번 선분), (2번 선분, 4번 선분), (2번 선분, 5번 선분)

(3번 선분, 4번 선분), (3번 선분, 5번 선분)

(4번 선분, 5번 선분)

이렇게 6가지 경우가 있다.

입력

첫 행에 선분의 개수 N (1 <= N <= 10,000)이 주어진다.

두 번째 행부터 N행에 걸쳐 각 선분의 정보 sx, sy, ex, ey (-1,000,000 <= sx, sy, ex, ey <= 1,000,000)가 공백으로 구분되어 주어진다.

출력

선분이 서로 만나거나 교차하는 모든 경우의 수를 구하여 출력한다.

예제1

예제2

예제3

출처

comkiwer

2차원 평면에서 두 선분이 만나는 경우의 수 2초 64MB