Use scanline y = -x + a We need to use no more than 6 points If you want to be fast use k-statistic in O(n) For better explanation write here: myironmistake@gmail.com
All AC solutions pass all of your tests. :) So I will not add them. But I have added a test from discussion at Codeforces and some more tests of similar structure.