1019: 圆交

题目

题目描述

本题将用到$k$维超球，或者说，$k$维超援。

在$k$维空间里有$n$个关键点。

现在给你两个球心$p_1$,$p_2$，和两个代价参数$v_1$,$v_2$。

我们要构建两个半径分别为$r_1$,$r_2$的$k$维超球使得尽可能多的关键点被这两个球包括(重复包含仅计算一次)，同时使得$v_1 * r_1^2 + v_2 * r_2^2 \le v $。 ($v$为阈值)

半径可以为$0$，此时超球退化成点。

输入格式

第一行五个整数$n,k,v,v_1,v_2$，含义同问题描述。

第二行$k$个整数$x_1,x_2,…,x_k$，表示$p_1$的坐标。

第三行$k$个整数$x_1,x_2,…,x_k$，表示$p_2$的坐标。

接下来$n$行，每行$k$个整数$x_1,x_2,…,x_k$，表示一个关键点的坐标。

输出格式

一行一个整数$ans$，表示能包含的最大关键点数量。

样例输入

Input 1

5 2 86 5 6 6 3 9 1 1 8 6 1 3 10 3 10 9 2

Input 2

10 10 749 3 7 2 3 4 6 1 3 2 10 7 4 2 4 5 1 6 9 9 9 4 3 7 9 9 1 1 3 3 4 6 10 4 7 3 6 5 5 3 3 4 5 4 4 5 3 10 3 4 8 7 5 9 1 3 9 1 2 1 6 7 8 7 1 1 2 5 8 8 9 6 4 9 6 1 2 9 8 1 2 9 5 3 5 4 6 9 5 8 8 6 5 7 1 5 6 10 8 10 4 9 10 10 6 3 10 2 9 4 9 2 6 9 8 5 4 1 7 4 5 7 7

样例输出

Output 1

2

Output 2

9

数据范围

对于$10\%$的数据，$n\le 10$；

对于$30\%$的数据，$n\le 5'000$；

对于$70\%$的数据，$n\le 500'000$；

对于$100\%$的数据，$n\le 1'000'000, k\le 10,x_i\le 10^5,v_1,v_2\le 10^6,v\le 2 * 10^{18},n * k\le 2'500'000$。

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！