#795. 三角形

三角形

问题描述

给出平面上 nn 个点,从中选择三个点,以它们为顶点形成一个三角形,要求这三个点不在同一条直线上,并且三角形的面积不超过 ss 。求有多少种不同的选择点的方案。

注意,如果选出的三个点中至少有两个点坐标相同,我们认为这三个点在同一条直线上。

可能会用到海伦公式:对于边长分别是 a,b,ca,b,c 的三角形,令 p=(a+b+c)/2p=(a+b+c)/2 ,则三角形面积 S=sqrt(p(pa)(pb)(pc))S=sqrt(p(p-a)(p-b)(p-c))

输入格式

第一行两个正整数 n,sn,s

接下来 nn 行,每行两个正整数 a,ba,b ,表示有一个坐标为 (a,b)(a,b) 的点 。

输出格式

输出一行一个数,表示方案的数量

样例输入

5 5
1 1
1 2
2 1
1 99
1 100

样例输出

2

样例解释

两种方案,一种方案是选择前三个点,另一种方案是选择后三个点。

数据规模和约定

对于 30%30\% 的数据,n4 n\le 4

对于 60%60\% 的数据, n10n\le 10

对于 100%100\% 的数据, n100,1s10000n\le 100,1\le s\le 10000 ,点的横纵坐标均在 11100100 之间 。