/ Vijos / 题库 /

黑白三角

黑白三角

描述

一天,小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

信息

ID
1486
难度
7
分类
动态规划 | 数据结构 | 线段树 点击显示
标签
(无)
递交数
60
已通过
12
通过率
20%
上传者

相关

在下列训练计划中:

RP++分类题库