Incidental Points
Time limit5sMemory limit128 MB
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 joining two points and connects them without extending beyond either endpoint. A third point is said to be incident to if it lies on the straight line through and and falls between them; in that case the segment is said to include . By definition, the endpoints and are themselves included in .
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 and with . 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 is the test case number (starting from 1), the period is followed by a single space, and is the number of points lying on the segment that includes the most points.