P10247 Solution

irris · 2024-03-10 15:06:31 · 题解

可以发现，很多点的答案都可以是 1。具体地，只有 x_i = x_1 或 y_i = y_1 的 i 才需要找到一个非 1 的 j，而这事实上已经有一维固定了，形态较为简单。

不妨假设有 x_i = x_1，对 y_i = y_1 是类似的。去除所有这样的元素，并且任取一个剩余的元素 (p, q)（若不存在，则说明所有答案都是 0），此时答案还不可能为 (p, q) 的则只有最多两个点，属性构成的不可重集分别为 \{x_1, p\} 与 \{x_1, q\}。

对这 O(1) 个特殊点暴力计算即可。总复杂度 O(n)。