2463: 三角形

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:47 解决:11

题目描述

给出平面上n个点,从中选择三个点,以它们为顶点形成一个三角形,要求这三个点不在同一条直线上,并且三角形的面积不超过s。求有多少种不同的选择点的方案。
注意,如果选出的三个点中至少有两个点坐标相同,我们认为这三个点在同一条直线上。
可能会用到海伦公式:对于边长分别是a、b、c的三角形,令p=(a+b+c)/2,则三角形面积S=sqrt(p(p-a)(p-b)(p-c))

输入

第一行两个正整数n、s,
接下来n行,每行两个正整数a、b,表示有一个坐标为(a,b)的点

输出

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

样例输入 复制

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

样例输出 复制

2

提示

【样例解释】
两种方案,一种方案是选择前三个点,另一种方案是选择后三个点。
【数据规模和约定】
对于30%的数据, n<=4
对于60%的数据, n<=10
对于100%的数据, n<=100,1<=s<=10000,点的横纵坐标均在1到100之间