Description

作为世界上最受尊敬的政治民意调查公司的员工，你必须将复杂的现实问题简化为几个数字。这并不总是容易的。一场重要的选举即将到来，应候选人 X 的要求，你刚刚完成了对 $n$ 人的民意调查。你从每个人那里收集了三条信息，第 $i$ 个人的信息记录为：

$a_i$ —— 他们记住的 $\pi$ 的位数

$b_i$ —— 他们头上的头发数量

$c_i$ —— 他们是否会投票给候选人 X

不幸的是，你开始怀疑这些问题是否真的最相关。事实上，你在数据中看不到 $a$、$b$ 和 $c$ 之间的任何相关性。当然，你不能直接反驳你的客户——那是丢掉工作的好方法！

也许答案是找到某种加权公式，使结果看起来有意义。你将选择两个实数 $S$ 和 $T$，并按测量值 $a_i \cdot S + b_i \cdot T$ 对民意调查结果 $(a_i, b_i, c_i)$ 进行排序。如果结果中 $c_i$ 为真的部分尽可能接近在一起，排序看起来会最好。更准确地说，如果 $j$ 和 $k$ 是 $c_i$ 为真的第一个和最后一个结果的索引，你希望最小化簇大小，即 $k-j+1$。注意，某些 $S$ 和 $T$ 的选择会导致 $(a_i, b_i, c_i)$ 三元组之间的平局。当这种情况发生时，你应该假设发生了最糟糕的排序（即最大化该 $(S, T)$ 对的簇大小）。

Input Format

输入以一行开始，包含 $n$ ($1 \leq n \leq 250,000$)，即调查的人数。接下来是每个被调查者的一行。每行包含整数 $a_i$ ($0 \leq a_i \leq 2,000,000$)、$b_i$ ($0 \leq b_i \leq 2,000,000$) 和 $c_i$，其中 $c_i$ 为 $1$ 表示该人将投票给候选人 X，否则为 $0$。输入保证至少有一个人会投票给候选人 X。

Output Format

输出所有可能的 $(S, T)$ 对中最小的簇大小。

6
0 10 0
10 0 1
12 8 1
5 5 0
11 2 1
11 3 0

4

10
6 1 1
0 2 0
2 1 1
6 1 1
8 2 0
4 4 0
4 0 0
2 3 1
6 1 0
6 3 1

8

5
5 7 0
3 4 0
5 7 0
5 7 1
9 4 0

1

Hint

时间限制：5000 毫秒，内存限制：1048576 kB。

国际大学生程序设计竞赛（ACM-ICPC）世界总决赛 2016。

题面翻译由 ChatGPT-4o 提供。