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

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

선분에 포함되는 점

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

요약
각 테스트 사례에서 주어진 점 중 두 개를 골라 그 선분이 포함하는 점의 수가 최대가 되도록 하고, 그 개수를 출력한다.
난이도

보통10점 중 7점

유형
기하, 해시맵, 수학, 완전 탐색
정답자
아직 제출이 없습니다

문제

직선(line)과 달리, 두 점 P1P_1, P2P_2 를 잇는 선분(segment) P1P2P_1P_2 는 두 점을 연결하되 끝점 바깥으로는 뻗어 나가지 않는다. 세 번째 점 P3P_3 가 P1P_1 과 P2P_2 를 지나는 직선 위에 있으면서 두 점 P1P_1, P2P_2 사이에 놓여 있으면, P3P_3 는 선분 P1P2P_1P_2 에 포함된다(incident)고 하고, 선분 P1P2P_1P_2 는 P3P_3 를 포함한다고 한다. 정의에 따라 두 끝점 P1P_1 과 P2P_2 자신도 선분 P1P2P_1P_2 에 포함된다.

평면 위에 주어진 점들 중 두 점을 골라 선분을 만들 때, 하나의 선분이 포함할 수 있는 주어진 점의 최대 개수를 구하는 프로그램을 작성하라.

입력

하나 이상의 테스트 케이스가 주어진다. 각 테스트 케이스는 서로 다른 두 개 이상의 점으로 이루어지며, 각 점의 데카르트 좌표가 한 줄에 두 정수 XX, YY 로 주어진다. 이때 0≤∣X∣, ∣Y∣<1060 \le |X|,\ |Y| < 10^6 이다. 한 테스트 케이스의 점 개수는 1000 개를 넘지 않는다. -(빼기 기호) 가 두 개 이상으로만 이루어진 줄은 한 테스트 케이스의 끝을 나타낸다. 마지막 테스트 케이스 뒤에는 - 가 두 개 이상인 줄이 하나 더 온다.

출력

각 테스트 케이스마다 결과를 한 줄에 다음 형식으로 출력한다.

k. n

여기서 kk 는 테스트 케이스 번호(1 부터 시작)이고, 마침표 뒤에는 공백이 하나 오며, nn 은 가장 많은 점을 포함하는 선분 위에 있는 점의 개수이다.

예제8

  1. 예제 1

    입력
    1 1
    1 5
    5 9
    9 5
    5 5
    3 2
    5 3
    ----
    1 5
    5 1
    1 1
    5 5
    --
    --------
    
    예상 출력
    1. 4
    2. 2
    
  2. 예제 2

    입력
    0 0
    3 4
    --
    --
    
    예상 출력
    1. 2
    
  3. 예제 3

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

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

    입력
    5 0
    5 1
    5 2
    5 10
    1 1
    9 9
    --
    --
    
    예상 출력
    1. 4
    
  6. 예제 6

    입력
    0 7
    2 7
    8 7
    100 7
    3 3
    --
    --
    
    예상 출력
    1. 4
    
  7. 예제 7

    입력
    0 0
    0 1
    1 0
    1 1
    --
    --
    
    예상 출력
    1. 2
    
  8. 예제 8

    입력
    0 0
    1 1
    2 2
    ----
    10 10
    20 20
    30 5
    7 7
    ----
    0 0
    0 5
    5 0
    --
    --------
    
    예상 출력
    1. 3
    2. 3
    3. 2