题目描述
给定 n 个点,第 i 个点的坐标为 (ai,bi),颜色为 ci。共有 k 种颜色,每种颜色至少出现一次。
定义两个点的差异值为
$$f(i,j)=\begin{cases}
(a_i-a_j)^2+(b_i-b_j)^2,&c_i\ne c_j,\\
0,&c_i=c_j.
\end{cases}$$
求最大的差异值。所有点颜色相同时,答案为 0。
输入格式
第一行两个整数 n,k。随后 n 行,每行三个整数 ai,bi,ci。
输出格式
输出一个整数,表示最大差异值。
数据范围
- 1≤k≤n≤250000。
- 0≤ai,bi≤109,1≤ci≤k。
- 每种颜色至少出现一次。题面未保证不同点的坐标互异。
样例
输入:
4 3
0 2 1
1 3 3
3 4 1
2 2 2
输出:
5
第 2、3 个点颜色不同,距离平方为 (1−3)2+(3−4)2=5,达到最大值。
官方附加样例说明
0b:n=k=2,(a1,b1)=(0,0),(a2,b2)=(109,109),ci=i。答案 2×1018。
0c:n=5000,k=1,ai=bi=i2+7,ci=1。答案 0。
0d:n=250000,k=2,ai=bi=2i,ci=(imod2)+1。答案 499996000008。
子任务
| 编号 |
附加限制 |
分值 |
| 1 |
n≤5000 |
3 |
| 2 |
所有 bi=0 |
8 |
| 3 |
k=n |
30 |
| 4 |
k=2 |
38 |
| 5 |
无附加限制 |
21 |