프로그램 명: coci_trokuti
제한시간: 1 초
좌표평면 상에 N개의 직선 (ax+by+c=0 꼴)이 주어져있다. 이 직선들로 이루어진 크고 작은 삼각형의 수를 구하는 프로그램을 작성하여라.
※ 두 직선이 겹치는 경우나 세 직선이 한 점에서 만나는 경우는 존재하지 않는다.
입력 형식
-
첫 번째 줄에는 직선의 수 N이 주어진다. (1 ≤ N ≤ 300,000)
-
두 번째 줄부터 N개의 줄에는 각 직선의 a, b, c 값이 주어진다. a, b, c는 절댓값이 10^9 이하인 정수이며, a, b 중 적어도 하나는 0이 아니다.
전체 데이터의 40%는 1 ≤ N ≤ 1,000 이다.
출력 형식
주어진 직선들로 이루어진 크고 작은 삼각형의 수를 출력한다. 답이 너무 클 수 있으므로 1,000,000,007로 나눈 나머지를 출력한다.
입력 예 1
6
0 1 0
-5 3 0
-5 -2 25
0 1 -3
0 1 -2
-4 -5 29
출력 예 1
10
입력 예 2
5
-5 3 0
-5 3 -30
0 1 0
3 7 35
1 -2 -1
출력 예 2
10
입력 예 1 설명
첫 번째 예제는 문제에서 주어진 그림과 같다.
You are given N lines, their equations being Ai x + Bi y + Ci = 0 in the coordinate plane. Calculate the
number of triangles whose sides lie on the given lines. Since the result can be very large, output the
number modulo 1 000 000 007.
Important note: No three lines will intersect at the same point.
입력
The first line of input contains the integer N (1 ≤ N ≤ 300 000), the number of lines.
Each of the following N lines contains three integers: Ai , Bi and Ci , the numbers defining the i th line. All numbers will be lesser than 109
.
출력
The first and only line of output must consist of the required number from the task.
A possible position of lines.
입출력 예
input
6
0 1 0
-5 3 0
-5 -2 25
0 1 -3
0 1 -2
-4 -5 29
output
10
input
5
-5 3 0
-5 -3 -30
0 1 0
3 7 35
1 -2 -1
output
10
Clarification of the first example: The example corresponds to the image in the task.
출처:/coci/2013-2014/contest5
번역:functionx
[질/답]
[제출 현황]
[푼 후(2)]