Under construction

Still being built. Things may change

Triangles

Interview

Time limit1sMemory limit1024 MB

Summary
Given N named points with integer coordinates, list every triple of points that is not collinear, with the names in input order.
Level

Easy2 of 10

Topics
Brute force, Geometry
Solved
No attempts yet

Problem

Given NN points in the plane, each with a name and coordinates. Write a program named triangles that finds all triangles that can be formed with three of the given points as vertices.

Input

The first line of standard input contains the integer NN, the number of points. Each of the next NN lines contains a name, the x-coordinate, and the y-coordinate of one point, in that order. A name is a single uppercase Latin letter. Both coordinates are integers in the range (−2000,2000)(-2000, 2000).

Output

On consecutive lines of standard output, print the names of the three points that form each triangle, separated by one space. List the vertices of each triangle in the order their names appear in the input. If the points form no triangle, print the text "No triangles."

Constraints

3≤N≤263 \le N \le 26

Examples2

  1. Example 1

    Input
    5
    A 0 0
    B 5 0
    C 0 4
    D 10 0
    E 0 8
    
    Expected output
    A B C
    A B E
    A C D
    A D E
    B C D
    B C E
    B D E
    C D E
    
  2. Example 2

    Input
    4
    X 0 0
    Y 3 3
    T 7 7
    W 4 4
    
    Expected output
    No triangles.