Halo Combat Evolved
All submissions for this problem are available.
Halo is a popular multiplayer game made by Microsoft Studios. Ragul.B, an amateur player, wants to be safe throughout the game by following some path in the map made up of location points, such that every player’s position in the map is included within the location points, i.e: the path is the smallest perimeter fence including all points. Help Ragul.B find the minimal set of location points , i.e: the path by which he can travel , such that other players can’t shoot him from behind.
Note: Other players are static , they retain their position.
First line contains the number of test cases T.
Following line has the number of location points N .
Following N lines will have location points (x,y).
For each test case, output the minimal path.
Input: 1 13 1 0 9 1 8 2 10 3 7 3 6 4 5 4 4 4 3 3 2 4 2 6 1 4 0 3 Output: 0,3 1,0 9,1 10,3 2,6 0,3
Note: Starting point and ending point are same , so they are repeated twice .All points in the path are displayed in counter clockwise direction along the path.
|Time Limit:||5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.