BUET Inter-University Programming Contest

Problem C – Counting Triangles

 

Problem

You are given a convex polygon of N vertices. Find how many ways three vertices can be chosen such that the triangle formed by those has an area not more than K.

 

Input

The first line of input contains T  which is the number of tests cases.  Each case contains two integers N  and K . Each of the next N lines will contain two integers: xi yi denoting i-th vertex of the polygon  The vertices will be given in anti-clockwise order.

 

Output

For each test case output one line the number of ways to choose a triangle from the vertices of the convex polygon whose area is not more than K.

Sample Input

Output for Sample Input

1

5 30

-5 -5

-2 -10

3 0

1 7

-2 4

7

 

Problemsetter:

Tasnim Imran Sunny

Special Thanks:

Shahriar Rouf Nafi