题目链接

题目描述

平面上有 $n$ 个点,每个点有三个属性 $(x,y,c)$,保证不存在两个不同的点,使得 $(x,y)$ 同时相同

求:

$$
\max_{i \neq j} \left( (x_i-x_j)^2+(y_i-y_j)^2+(x_i-x_j) \times (y_i-y_j) \right)
$$

其中 $2 \le n \le 2 \times 10^5, -10^9 \le x,y \le 10^9, 1 \le c \le n$

题解

并不会正解……

考虑骗分,用 kd-tree 搞一下,查询的时候就查一下矩形的四个角是否都比当前答案劣

然后……就过了……