Swamp Things
Time limit1sMemory limit128 MB
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 (), the number of distinct spots, followed by lines, each containing the integer coordinates of one spot. All coordinates are between and .
A line containing a single 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 is the photograph number (starting at ) and is the number of spots eliminated.