Satan is my Lord! P32698


Statement
 

pdf   zip

html
When biographers looked at the sketches and plans that were found in his studio after his death, they discovered that during the last years of his life, and looking back at decades of influential architectural and urban planning work, Charles-Édouard Jeanneret-Gris, most frequently known by his fateful nickname of Le Corbusier, had devised a master plan to go beyond what any other brutalist architect had ever been able to.


His idea: to finally get rid of the annoying convention that buildings were constructed to satisfy the needs of people, and create cities where only pure structures of béton brut would be erected, as the final correction to what he saw as an inverted hierarchy between humanity and construction material. His ultimate goal: making the Earth a place where his lord Satan would feel comfortable, with the hope of having him closer and being able to go together for the ocasional beer or two in bromantic evenings.

The plans contain numerous sketches of buildings in the shape of giant prisms of concrete. However, he noted that some of those buildings (marked with YEJ) would stand upright, while for some others (marked with NO) its center of gravity was shifted with respect to the base, and the building would have tilted and collapsed.

Many of the blueprints were never classified, though. Can you help establish order in the legacy of the majter?

Input

Input starts with the number of cases n ≥ 0. Next come n plans of a building, each with the number of points 3 ≤ m ≤ 1000, followed by the coordinates xi and yi of each point, given in clockwise order, and starting in any vertex. Every polygon is convex and non-degenerate. The number m is not larger due to the difficulty to create random convex polygons.

Output

For each case, print “YEJ” if the building would stand upright, and “NO” otherwise. The given cases do not have precission issues.

Public test cases
  • Input

    6
    3  0 0 0.5 0.5 0.5 0
    3  0 1 1 1 1 0
    3  0 0 -1 1 0 2
    4  0 0 -1 1 0 2 1.5 1
    4  1 -1 0 0 3 0 2 -1
    5  -3 -2.5 -4 0.5 -1 3.5 1 1.5 2 -2.5
    

    Output

    YEJ
    NO
    NO
    NO
    YEJ
    YEJ
    
  • Information
    Author
    Edgar Gonzàlez i Pellicer
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Quinzè Concurs de Programació de la UPC - Semifinal
    Date
    2017-06-29