Under construction

Still being built. Things may change

Swamp Things

Time limit1sMemory limit128 MB

Summary
For each test case, count how many of up to 1000 points lie on a single line chosen as the one containing the most points, but only if that maximum count is at least four.
Level

Medium6 of 10

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

Problem

A photograph is a set of bright spots on a black background, given as points in the plane. Some of the spots are lights from train windows, and the train runs along a perfectly straight track, so those spots are collinear.

To remove them, find the line that passes through the most spots. If four or more spots lie on that line, eliminate all of the spots on it (they are assumed to be train windows). If two or more lines are tied for the most spots, any one of them may be chosen, but the number of eliminated spots is the same either way. If no line passes through four or more spots, assume there is no train and eliminate nothing.

For each photograph, report how many spots are eliminated.

Input

The input is a series of test cases. Each test case describes one photograph: a line with a positive integer nn (n≤1000n \le 1000), the number of distinct spots, followed by nn lines, each containing the integer coordinates xx yy of one spot. All coordinates are between 00 and 1000010000.

A line containing a single 00 follows the last photograph and must not be processed.

Output

For each photograph, output one line of the form Photo k: c points eliminated, where kk is the photograph number (starting at 11) and cc is the number of spots eliminated.

Examples2

  1. Example 1

    Input
    6
    0 1
    0 2
    1 2
    2 2
    4 5
    5 6
    4
    3 5
    4 4
    6 5
    7 4
    0
    
    Expected output
    Photo 1: 4 points eliminated
    Photo 2: 0 points eliminated
    
  2. Example 2

    Input
    6
    0 0
    1 0
    2 0
    3 0
    5 7
    8 2
    0
    
    Expected output
    Photo 1: 4 points eliminated