黑白三角
测试数据来自 system/1486
描述
一天,小m在平面上画了N个黑点和N个白点,按以下方式来连边,构成一个有向完全图。
1.I J同色,随机选择I→J或J→I
2.I J异色,若Dij>D,则白点→黑点,否则黑点→白点
这里的Dij指的是曼哈顿距离(|xi-xj|+|yi-yj|),D为给定值
然后,小m发现有很多三角形很漂亮,漂亮三角形的定义如下:
1.三个顶点I J K颜色不完全相同
2.它们之间的连的边是 I→J J→K K→I
请你求出漂亮三角形至少有多少个,至多有多少个。
格式
输入格式
第一行两个正整数 N D
接下来N行Xi Yi描述第i个白点的坐标
再接下来N行Xj Yj描述第j个黑点的坐标
输出格式
两个数依次为漂亮三角形最少时的个数,最多时的个数,中间用一个空格隔开。
样例1
样例输入1
2 1
1 2
1 1
3 1
2 2
样例输出1
0 2
限制
1s
提示
忽略三点共线
N <= 100000
来源
mt