점들

시간 제한1초메모리 제한128 MB

요약
3차원 공간에 주어진 점들 중 적어도 세 개를 지나는 서로 다른 직선의 개수를 센다.
난이도

보통10점 중 7점

유형
기하, 해시맵, 수학, 구현
정답자
아직 제출이 없습니다

문제

당신과 친구들은 3차원 공간에 특정 규칙에 따라 점을 놓는 "Trivial Points"라는 게임을 만들었습니다. 이 게임의 컴퓨터 버전을 만들기 위해, 3차원 공간의 점 집합이 주어졌을 때 주어진 점들 중 3개 이상을 지나는 서로 다른 직선의 개수를 세는 프로그램을 작성하세요.

입력

첫째 줄에 점의 개수 nn이 주어진다. 이어지는 nn개의 줄에는 각 점의 세 정수 좌표 xix_i, yiy_i, ziz_i가 공백 하나로 구분되어 주어진다.

출력

주어진 점들 중 3개 이상을 지나는 서로 다른 직선의 개수를 정수 하나로 출력한다.

제한

  • 4≤n≤10004 \le n \le 1000
  • xi,yi,zix_i, y_i, z_i는 정수
  • −10000≤xi,yi,zi≤10000-10000 \le x_i, y_i, z_i \le 10000
  • 모든 점은 서로 다르다.

힌트

예시에서 한 직선은 일직선 위에 있는 네 점 (−5,−5,−5)(-5, -5, -5), (1,1,1)(1, 1, 1), (2,2,2)(2, 2, 2), (3,3,3)(3, 3, 3)을 지나고, 다른 한 직선은 (1,0,−1)(1, 0, -1), (2,2,2)(2, 2, 2), (3,4,5)(3, 4, 5)를 지난다. 두 직선 모두 3개 이상의 점을 지나며(점 (2,2,2)(2, 2, 2)는 두 직선 위에 동시에 놓인다), 따라서 답은 22이다.

예제1

  1. 예제 1

    입력
    7
    1 0 -1
    3 4 5
    2 2 2
    3 3 3
    -5 -5 -5
    1 1 1
    -3 4 0
    
    예상 출력
    2