题目描述

As an employee of the world’s most respected political polling corporation, you must take complex, real-world issues and simplify them down to a few numbers. It isn’t always easy. A big election is coming up and, at the request of Candidate X, you have just finished polling $n$ people. You have gathered three pieces of information from each person, with the values for the $i^\text {th}$ person recorded as:

$a_ i$ – the number of digits of $\pi$ they have memorized

$b_ i$ – the number of hairs on their head

$c_ i$ – whether they will vote for Candidate X

Unfortunately, you are beginning to wonder if these are really the most relevant questions to ask. In fact, you cannot see any correlation between $a$, $b$, and $c$ in the data. Of course, you cannot just contradict your customer – that is a good way to lose your job!

Perhaps the answer is to find some weighting formula to make the results look meaningful. You will pick two real values $S$ and $T$, and sort the poll results $(a_ i, b_ i, c_ i)$ by the measure $a_ i \cdot S + b_ i \cdot T$. The sort will look best if the results having $c_ i$ true are clustered as close to each other as possible. More precisely, if $j$ and $k$ are the indices of the first and last results with $c_ i$ true, you want to minimize the cluster size which is $k-j+1$. Note that some choices of $S$ and $T$ will result in ties among the $(a_ i,b_ i,c_ i)$ triples. When this happens, you should assume the worst possible ordering occurs (that which maximizes the cluster size for this $(S, T)$ pair).

输入格式

The input starts with a line containing $n$ ($1 \leq n \leq 250\, 000$), which is the number of people polled. This is followed by one line for each person polled. Each of those lines contains integers $a_ i$ ($0 \leq a_ i \leq 2\, 000\, 000$), $b_ i$ ($0 \leq b_ i \leq 2\, 000\, 000$), and $c_ i$, where $c_ i$ is $1$ if the person will vote for Candidate X and $0$ otherwise. The input is guaranteed to contain at least one person who will vote for Candidate X.

输出格式

Display the smallest possible cluster size over all possible $(S, T)$ pairs.

题目大意

大选要到了，受候选人X的要求，你调查了 $n$ 个人，并记录了每个人的 $3$ 个信息：

• $a_i$ 他们能记忆 $\pi$ 的多少位
• $b_i$ 他们的头发数量
• $c_i$ 他们是否会给候选人X投票

你需要找到某个公式使这些结果看起来有意义。你要选择 $2$ 个实数 $S$ 和 $T$，将所有调查结果按 $a_i\times S+b_i\times T$ 排序。如果 $c_i$ 为 true 的人聚集在了一起，你会觉得这个排序看起来不错。更准确地说，如果 $j$ 和 $k$ 分别是第一个和最后一个 $c_i$ 为 true 的人的下标，你想要最小化 $k-j+1$。注意有些 $S$ 和 $T$ 会让排序时出现相等的情况，这时你应该假设最坏情况发生，即排序使得 $k-j+1$ 最大。

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

提示

Time limit: 5000 ms, Memory limit: 1048576 kB.

International Collegiate Programming Contest (ACM-ICPC) World Finals 2016