#P17074. [PA2015 Final]Trójkąty

    ID: 16275 传统题 10000ms 256MiB 尝试: 1 已通过: 1 难度: 6 上传者: 标签>CF2000提高欧几里得算法自定义排序规则叉积二分查找

[PA2015 Final]Trójkąty

题目描述

平面上给定 nn 个点。我们感兴趣的是,以这些点为顶点的直角三角形中,面积落在区间 [A,B][A, B] 内的三角形数量。

输入格式

第一行包含三个整数 n,A,Bn, A, B (1≤n≤2000,1≤A≤B≤1018)(1 \leq n \leq 2000, 1 \leq A \leq B \leq 10^{18})。

接下来的 nn 行描述各个点。其中第 ii 行包含两个整数 xi,yix_{i}, y_{i} (−109≤xi,yi≤109)(-10^{9} \leq x_{i}, y_{i} \leq 10^{9}),表示第 ii 个点的坐标。输入中给出的点不会重复。

输出格式

在一行中输出以给定点为顶点、且面积落在区间 [A,B][A, B] 内的直角三角形数量。

7 5 25
0 0
2 0
0 2
10 0
0 10
3 3
3 -3

3