Police in a Line
InterviewTime limit1sMemory limit128 MB
Decide whether any three of up to 300 given points are collinear, repeating for each dataset in the input.
- Level
Medium4 of 10
- Topics
- Geometry, Brute force
- Solved
- No attempts yet
Problem
Police work sometimes puts officers in real danger, and holding a cordon against a large protest such as the one at the IMF and World Bank meeting is one of those times. To keep injuries down, every officer is issued a safety code called the Guidelines for Extremely Fast Crowd Crushes, SMRT for short.
It kept happening that when protesters threw something at the cordon, the officer in front dodged it and the officer behind him, who could not see past the first one, took the hit. One of the guidelines written for officers who block a crowd therefore says that officers must not stand in a row, so that a heavy object such as a paving stone cannot find an easy target. Guidelines exist to be followed, so compliance has to be checked and every breach reported at once. Commanding officers cannot be everywhere, so the police need a tool that finds the breaches on its own. Writing that tool is your task.
A camera at every operation films the cordon from above, which lets you give each officer a coordinate in an imaginary coordinate system. An officer is identified by exactly one pair of integers and with . Corner positions are tactically bad, so no officer ever stands at .
Write a program that reads the coordinates of a cordon and finds out whether more than two officers stand on one straight line anywhere. The rule is fairly new and has not sunk in yet, so several lines may carry three or more officers. Morale and training are good enough that a single line never holds more than ten of them.
Input
The input holds several datasets. Each dataset starts on a new line, consists of the coordinates of 3 to 300 points, and ends with a pair of zeros (0 0). One point is given as two integers between 0 and 9999. A dataset may be split over several lines, but a coordinate pair is never split: a break always falls between two whole pairs. The whole input ends with one more pair of zeros.
Output
If no three officers stand on one straight line, print the single line Smernice byla dodrzena.. Otherwise print Tito policiste porusuji smernici: first, and then on each following line all officers who stand on one straight line. Every straight line carrying three or more officers has to appear, none may be left out. Inside one output line the coordinates are sorted by first, and by when the values are equal. Every point is wrapped in parentheses with its two components separated by a comma and no spaces. Nothing separates one point from the next apart from the parentheses. The output lines are ordered the same way the coordinates inside them are: by the first point, and when the first points are equal, by the second point, then the third, and so on. One officer can appear on several output lines. After each dataset, including the last one, print one blank line.