Well people, I've made corrections to my post. I'd made a silly mistake.Nothing controversial here.

The solution:
 Take the first sample test case:
2 10
3
3 20
1 5
2 11

The max linear size of the hole is 10*root(2).
3 20: Min linear size of the cover is 20*root(3)/2. (doesnt pass through)
This is because the triangle can be tilted such that it passes with its projection being 20/root(2)=10*root(2).
1 5: min linear size=10 i.e. the diameter(passes through)
2 11: Min linear size=11 i.e. side of the square.(passes through)

Hence the answer is 2.


Edited by author 03.12.2007 16:48

for triangle a*sqrt(3)/2

I've made changes to the post. Thanks for the clarification.