This page is still under construction.

Parts of this page are still being built. What you see may change.

Incidental Points

Time limit5sMemory limit128 MB

Summary
For each test case, choose two points whose segment contains the most other given points and report that count.
Level

Medium7 of 10

Topics
Geometry, Hash map, Math, Brute force
Solved
No attempts yet

Problem

Unlike a line, the segment P1P2P_1P_2 joining two points P1P_1 and P2P_2 connects them without extending beyond either endpoint. A third point P3P_3 is said to be incident to P1P2P_1P_2 if it lies on the straight line through P1P_1 and P2P_2 and falls between them; in that case the segment P1P2P_1P_2 is said to include P3P_3. By definition, the endpoints P1P_1 and P2P_2 are themselves included in P1P2P_1P_2.

Given a set of points in the plane, choose two of them to form a segment. Write a program that finds the largest number of the given points that a single such segment can include.

Input

Your program is tested on one or more test cases. Each test case is a set of two or more distinct points; the Cartesian coordinates of each point are given on their own line as two integers XX and YY with 0≤∣X∣, ∣Y∣<1060 \le |X|,\ |Y| < 10^6. No test case contains more than 1000 points. A line consisting of two or more - (minus signs) marks the end of a test case. One additional line of two or more - follows the last test case.

Output

For each test case, print the result on a single line in the format k. n, where kk is the test case number (starting from 1), the period is followed by a single space, and nn is the number of points lying on the segment that includes the most points.

Examples8

  1. Example 1

    Input
    1 1
    1 5
    5 9
    9 5
    5 5
    3 2
    5 3
    ----
    1 5
    5 1
    1 1
    5 5
    --
    --------
    
    Expected output
    1. 4
    2. 2
    
  2. Example 2

    Input
    0 0
    3 4
    --
    --
    
    Expected output
    1. 2
    
  3. Example 3

    Input
    0 0
    1 2
    2 4
    3 6
    4 8
    --
    --
    
    Expected output
    1. 5
    
  4. Example 4

    Input
    -3 -3
    -1 -1
    0 0
    2 2
    1 -4
    -4 1
    --
    --
    
    Expected output
    1. 4
    
  5. Example 5

    Input
    5 0
    5 1
    5 2
    5 10
    1 1
    9 9
    --
    --
    
    Expected output
    1. 4
    
  6. Example 6

    Input
    0 7
    2 7
    8 7
    100 7
    3 3
    --
    --
    
    Expected output
    1. 4
    
  7. Example 7

    Input
    0 0
    0 1
    1 0
    1 1
    --
    --
    
    Expected output
    1. 2
    
  8. Example 8

    Input
    0 0
    1 1
    2 2
    ----
    10 10
    20 20
    30 5
    7 7
    ----
    0 0
    0 5
    5 0
    --
    --------
    
    Expected output
    1. 3
    2. 3
    3. 2