Random Simple Polygon
Author: Ilham Winata Kurnia
This part of review is writen by the author himself (Ilham Winata Kurnia).
Given N collinear points, it is always possible to form a simple polygon using all the N points. Here we show two solutions (there are others) to solve this problem.
The first one is to pick one extreme point (e.g. the lowermost point) and sort the other points based on the angle formed by the segment connecting the extreme point and the other points and a horizontal segment going through the extreme point. Using the sorted points, we can obtain a parachute-like polygon.
The second way is to, first, create a bottom/top half convex hull from the points (other variation using left/right half is also possible), and then sort the remaining points by its x-coordinates. Join the remaining points appropriately to form the desired polygon.
Both of this solutions have O(N log N) implementations, which run well within the 1 second time limit. Due to the nice constraints, the only caution needed is when doing the arithmetics since the calculation does not fit into 32 bit integers.
This problem was solved by 13 teams. The first team to solve this problem: SYSU_Blover from Zhongsan (Sun Yat-sen) University, minute 34.