EppsNet Archive: Graham Scan

Competitive Programming: SPOJ – Build the Fence

 

At the beginning of spring all the sheep move to the higher pastures in the mountains. If there are thousands of them, it is well worthwhile gathering them together in one place. But sheep don’t like to leave their grass-lands. Help the shepherd and build him a fence which would surround all the sheep. The fence should have the smallest possible length! Assume that sheep are negligibly small and that they are not moving. Sometimes a few sheep are standing in the same place. If there is only one sheep, it is probably dying, so no fence is needed at all … Input t [the number of tests <= 100] [empty line] n [the number of sheep <= 100000] x1 y1 [coordinates of the first sheep] … xn yn [integer coordinates from -10000 to 10000] [empty line] [other lists of sheep] Text grouped in [ ] does not appear in the input file.… Read more →