아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

구슬 찾기

면접 대비

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

요약
테스트 케이스마다 서로 다른 정수 좌표 점을 최대 99개 주고 한 직선 위에 놓인 점의 최대 개수를 출력합니다.
난이도

보통10점 중 5점

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

문제

친구들이 "구슬 찾기" 놀이를 한다. 바닥에 구슬을 한 줌 흩뿌리고, 각 구슬의 위치는 평면 위의 정수 좌표로 나타낸다. 참가자는 직선 하나를 골라 그 위를 걸으면서 구슬을 줍는다. 그래서 고른 직선 위에 놓인 구슬만 주울 수 있다. 한 직선에서 구슬을 가장 많이 주운 사람이 이긴다. 우승자가 주운 구슬이 몇 개인지 구하라.

입력

첫째 줄에 테스트 케이스의 개수 TT가 주어진다. 각 테스트 케이스의 첫째 줄에는 구슬의 개수 NN이 주어지고, 1<N<1001 < N < 100이다. 이어지는 NN개 줄에는 구슬 하나의 좌표를 나타내는 두 정수가 공백으로 구분되어 주어진다. 같은 좌표가 두 번 주어지는 경우는 없다.

출력

각 테스트 케이스마다 Case #x: M 형식으로 한 줄을 출력한다. xx는 1부터 시작하는 테스트 케이스 번호이고, MM은 한 직선 위에 놓인 구슬의 최대 개수다.

예제1

  1. 예제 1

    입력
    2
    5
    1 1
    2 2
    3 3
    5 10
    6 11
    3
    4 5
    6 7
    8 8
    
    예상 출력
    Case #1: 3
    Case #2: 2