Logo CSP.ac

CSP.ac

1 s / 256 MB

#121. 【冬令营】Day2T1-三角形

统计

【问题描述】

给出平面上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之间