SIMPPOLY- Editorial

Triangulate and print 500 of those segments

Find any line joining two vertices of polygon that lies completely inside the polygon.

This line segments divides the polygon into two smaller polygons, so recurse on the polygon till you achieve 500 line segments.

Find a convex angle A in the polygon. Let B and C be it’s adjacent vertices in the polygon. Then find the nearest vertex D of the polygon that lies inside the triangle ABC and is closest to A (not euclidean distance, but distance parallel to the line BC).

If no point exists in the triangle ABC, then the line segment BC is the required line segment. Otherwise line segment is AD.

Add some nice polygons too.