Satan is my Lord! P32698


pdf   zip

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 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.


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

    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


  • Information
    Edgar Gonzàlez i Pellicer
    Official solutions
    User solutions
    Quinzè Concurs de Programació de la UPC - Semifinal