a bit of topcoder: SRM 633 Div. 1

(My first Div 1, OMG damn difficult)

First Problem (250 pts)
Problem Statement
633 Div. 1 250 - PeriodicJumping

Summary:
Can u build a polygon with a periodic sequence of segments \(a_1,a_2,a_3,\ldots,a_t\) by using the segments sequentially? If so, what is the minimum segments needed?

Solution:
Firstly it is always possible to build a polygon using these segments. Secondly, to solve this problem we need to know the "Polygon Inequality", which is a generalization of Triangle Inequality:

Triangle Ineq: \(a\leq b\leq c\) are the sides of a triangle if and only if \(c \leq a+b\)
Extended to polygons (by Induction I suppose)
Polygon Ineq: \(a_1,a_2,\ldots, a_n\) are sides of polygons iff the max side is \(\leq\) the sum of the rest of the sides.

So to build the polygon, we have to iterate through the segments one by one until we manage to fulfill the inequality. The idea sounds simple but whenever it is computational geometry, there are corner cases that must be taken care of..