Under construction

Still being built. Things may change

Police in a Line

Interview

Time limit1sMemory limit128 MB

Summary
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 XX and YY with 0≤X,Y≤99990 \le X, Y \le 9999. Corner positions are tactically bad, so no officer ever stands at (0,0)(0, 0).

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 xx first, and by yy when the xx 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.

Examples2

  1. Example 1

    Input
    5 5 8 7 14 11 4 8 20 15
    12 6 18 21 0 0
    5 5 8 8 14 13 0 0
    5 5 25 17 20 23 10 11 20 14 15 11 0 0
    0 0
    
    Expected output
    Tito policiste porusuji smernici:
    (4,8)(8,7)(12,6)
    (5,5)(8,7)(14,11)(20,15)
    (12,6)(14,11)(18,21)
    
    Smernice byla dodrzena.
    
    Tito policiste porusuji smernici:
    (5,5)(10,11)(20,23)
    (5,5)(15,11)(20,14)(25,17)
    
    
  2. Example 2

    Input
    1 1 2 2 3 3 0 0
    1 1 2 2 3 4 0 0
    0 0
    
    Expected output
    Tito policiste porusuji smernici:
    (1,1)(2,2)(3,3)
    
    Smernice byla dodrzena.