3 of 8
added 417 characters in body; edited title
Rainbolt
  • 6.4k
  • 6
  • 33
  • 62

Sort Walking Points

Reorder a list of points so that no lines drawn between the points in that order intersect.

Example Input

Read from STDIN, one point per line, in the format x y separated by a single space.

0 0
4 4
0 4
4 0

Example Output

0 0
0 4
4 4
4 0

Drawing three lines from (0,0) -> (0,4) -> (4,4) -> (4,0) would not cause any interesting lines, and so this output would be VALID, but it is not the only valid output for the example input.

Rules and Assumptions

  • You may start from any point.
  • Points and lines are plotted and drawn using a Cartesian Coordinate System
  • The number of points will be between 3 and 100 (inclusive)
  • Every input will be solvable

For further help: http://prntscr.com/3ayjys

diagram

Nacib Neme
  • 205
  • 2
  • 4