COCI 2013/2014 - Contest 5- 삼각형 만들기 (TROKUTI) > 문제은행 : 정보올림피아드&알고리즘




2685 : 삼각형 만들기 (TROKUTI)

제한시간
1000 ms   
메모리제한
32 MB   
해결횟수
11 회   
시도횟수
55 회   

문제

좌표평면 상에 N개의 직선 (ax+by+c=0 꼴)이 주어져있다. 이 직선들로 이루어진 크고 작은 삼각형의 수를 구하는 프로그램을 작성하여라.



※ 두 직선이 겹치는 경우나 세 직선이 한 점에서 만나는 경우는 존재하지 않는다.


입력형식

첫 번째 줄에는 직선의 수 N이 주어진다. (1 ≤ N ≤ 300,000) 두 번째 줄부터 N개의 줄에는 각 직선의 a, b, c 값이 주어진다. a, b, c는 절댓값이 109< 이하인 정수이며, a, b 중 적어도 하나는 0이 아니다. 전체 데이터의 40%는 1 ≤ N ≤ 1,000 이다.

출력형식

주어진 직선들로 이루어진 크고 작은 삼각형의 수를 출력한다. 답이 너무 클 수 있으므로 1,000,000,007로 나눈 나머지를 출력한다.

입력 예

6
0 1 0
-5 3 0
-5 -2 25
0 1 -3
0 1 -2
-4 -5 29

출력 예

10


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP