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

Edited by author 06.08.2019 18:42

NOTE: m >= 3

always m = 5. only special case m = 4!

Edited by author 23.10.2011 10:26

Tests for this problem are weak (e.g. see here: http://codeforces.ru/blog/entry/2920#comment-59153 )

I think you can try to add the following tests:
5 1
1 0
1 2
2 1
3 0
3 2

5 2
1 0
1 2
2 1
3 0
3 2

3 1
0 0
0 1
0 2

3 1
0 0
1 0
2 0


3 2
0 0
0 1
0 2

3 2
0 0
1 0
2 0

Edited by author 22.10.2011 22:51