P9658 [ICPC 2021 Macao R] Laser Trap

最近，BaoBao 正在玩著名的游戏 $Elden Ring$。这是一款开放世界游戏，你可以控制角色在各个地方旅行。然而，你的角色也可能会进入陷阱，你需要想办法逃脱。现在，BaoBao 的角色被困在一个有致命激光的二维平面上。平面上有 $n$ 个激光发生器（每个可以看作一个点），它们之间的每一对都会发射激光束（因此总共有 $\frac{n(n-1)}{2}$ 条激光束）。这些激光束从发生器点开始并在发生器点结束，不会延伸到无限远。 从点 $(0,0)$ 开始，BaoBao 想要逃到点 $(10^{10^{10^{10^{10}}}}, 10^{10^{10^{10^{10}}}})$，而不触碰任何激光束或发生器。为了做到这一点，BaoBao 可以请求她的朋友 DreamGrid 移除任意数量的激光发生器，以及从这些发生器开始或结束的任何激光束。输出为逃脱所需移除的最小激光发生器数量。 注意，BaoBao 不需要沿特定方向移动以逃脱。如果有必要，她的逃生路线甚至可以是曲线。

有多个测试用例。输入的第一行包含一个整数 $T$，表示测试用例的数量。对于每个测试用例： 第一行包含一个整数 $n$ ($1 \le n \le 10^6$)，表示激光发生器的数量。 接下来的 $n$ 行中，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$ ($-10^9 \le x_i, y_i \le 10^9$)，表示第 $i$ 个激光发生器的位置。 保证没有两个发生器重合，并且没有激光束或发生器会接触到 $(0,0)$。 还保证所有测试用例的 $n$ 的总和不超过 $10^6$。

对于每个测试用例，输出一行，包含一个整数，表示需要移除的最小发生器数量。

第二个和第三个样例测试用例如下所示。实心点和线代表剩余的激光发生器和光束，而空心点和虚线代表被移除的激光发生器和光束。箭头是逃生路线。   题面翻译由 ChatGPT-4o 提供。