#P1995. Vijos1486 Triangle

    ID: 1018 传统题 1000ms 64MiB 尝试: 81 已通过: 11 难度: 7 上传者: 标签>CF2300提高+/省选-贡献法交换求和顺序排序贪心坐标变换滑动窗口树状数组离散化

Vijos1486 Triangle

题目描述

一天,小m在平面上画了N个黑点和N个白点,按以下方式来连边,构成一个有向完全图。 1. i和j同色,随机选择 i→ji\to j 或 j→ij\to i。 2. i和j异色,若 D(i,j)>DD(i, j)>D,则白点→\to 黑点,否则黑点→\to 白点。 这里的 D(i,j)D(i, j) 指的是曼哈顿距离 (∣xi−xj∣+∣yi−yj∣)(|x_i-x_j|+|y_i-y_j|),DD 为给定值。 然后,小m发现有很多三角形很漂亮,漂亮三角形的定义如下: 1. 三个顶点i、j和k颜色不完全相同 2. 它们之间的连的边是i→j、j→k、k→ii\to j、j\to k、k\to i。 请你求出漂亮三角形至少有多少个,至多有多少个。

输入格式

第一行两个正整数N和D,接下来N行Xi Yi描述第i个白点的坐标,再接下来N行Xj Yj描述第j个黑点的坐标。其中0≤D,∣X∣,∣Y∣≤1080 ≤ D, |X|, |Y| ≤ 10^8。

输出格式

两个数依次为漂亮三角形最少时的个数,最多时的个数,中间用一个空格隔开。

2 1
1 2
1 1
3 1
2 2

0 2

提示

对于10%的数据满足:N ≤ 5

对于40%的数据满足:N ≤ 1,000

对于100%的数据满足:N ≤ 100,000

题目来源

By Mt