만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

행성의 정렬

면접 대비

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

요약
격자 위의 점 N개가 주어질 때, 한 직선 위에 놓인 세 점을 모두 찾아 ID 순서대로 정렬하여 출력합니다.
난이도

쉬움10점 중 3점

유형
기하, 완전 탐색, 정렬
정답자
아직 제출이 없습니다

문제

실제로 이 문제는 풀을 뜯고 있는 NN 마리 (1≤N≤7701 \le N \le 770) 소의 정렬에 관한 것이다. 소에는 11번부터 NN번까지 번호가 붙어 있다. 들판의 크기는 약 15000×1500015000 \times 15000이고, 소의 위치는 모두 정수 x,yx, y 좌표로 주어진다. 좌표 범위는 00 이상 1500015000 이하이다.

Bessie는 고개를 들었다가 Sara, Julie와 정확히 일직선으로 늘어선 것을 발견한다. 그녀는 들판에 일직선으로 늘어선 세 마리 소의 조가 몇 개인지 궁금해한다.

모든 소의 위치가 주어졌을 때(같은 위치에 있는 소는 없다), 정확히 일직선을 이루는 세 마리 소의 집합을 모두 구하라. 각 집합은 번호가 작은 소부터 정렬한다. 집합들은 세 번호가 작은 순서대로 정렬하며, 첫 번째 번호가 같으면 두 번째, 세 번째 번호로 비교한다.

입력

첫 줄에 정수 NN이 주어진다.

둘째 줄부터 N+1N+1번째 줄까지 각 줄에는 ii번 소의 xx 좌표와 yy 좌표가 공백으로 구분되어 주어진다.

출력

첫 줄에 정확히 일직선인 세 마리 소 집합의 개수를 출력한다. 네 마리가 일직선이면 그 네 마리로 만들어지는 세 마리 집합이 4개이다.

둘째 줄부터 일직선인 집합마다 세 소의 번호를 공백으로 구분해 한 줄에 출력한다. 줄은 위에서 정한 순서로 정렬한다. 일직선인 집합이 없으면 첫 줄 뒤에 아무것도 출력하지 않는다.

예제1

  1. 예제 1

    입력
    8
    0 0
    0 4
    1 2
    2 4
    4 3
    4 5
    5 1
    6 5
    
    예상 출력
    1
    1 3 4