题目描述

上海超级计算机公司作为全球最大的计算机芯片制造商，发明了一类新型纳米粒子——两亲性碳分子（ACMs）。ACMs 是半导体材料，这意味着它们既可以作为电子的导体，也能成为绝缘体，因而具备对计算机芯片行业至关重要的特性。同时，它们属于两亲性分子，即分子的某些部分具有亲水性，而其他部分具有疏水性。

• 亲水性 ACMs 可溶于极性溶剂（例如水），但不溶于非极性溶剂（例如丙酮）；
• 疏水性 ACMs 则相反，可溶于丙酮，却不溶于水。

溶解在水或丙酮中的半导体 ACMs 可用于计算机芯片的制造过程。

作为上海超级计算机公司的材料工程师，你的工作是利用 ACM 粒子制备 ACM 溶液。每天早上 8 点到工厂时，工作台上会有一批 ACM 粒子。制备溶液的方法是：向这些粒子中滴入一些水和丙酮，观察 ACMs 溶解于溶剂的过程。为了制备未混合的溶液，需先将一块绝缘碳分隔卡（ICPC）垂直于工作台放置，以分隔 ACM 粒子。ICPC 足够长，能够完全分隔粒子。随后，在 ICPC 的一侧滴入水，另一侧滴入丙酮。如此一来，ICPC 能使一侧得到溶于水的亲水性 ACMs，另一侧得到溶于丙酮的疏水性 ACMs。若 ICPC 恰好放置在某些 ACM 粒子的上方，这些 ACMs 会处于水溶液和丙酮溶液的边界处并溶解。图 1 展示了你的工作场景。

由于日常工作过于简单乏味，主管增加了一些挑战，要求你尽可能让更多的 ACMs 溶解到溶液中。你知道，ICPC 的放置位置至关重要，因为若亲水性 ACMs 位于丙酮一侧，或疏水性 ACMs 位于水一侧，它们都不会溶解。作为经验丰富的工程师，你意识到有时很难找到 ICPC 的最佳位置，因此决定编写程序来提供帮助。你已请主管购买了一台特殊的数码相机，安装在工作台上方，这样程序就能从相机拍摄的二维图像中获取每个 ACM 粒子的精确位置和种类（亲水性或疏水性）。在二维图像中，放置在工作台上的 ICPC 会呈现为一条直线。

输入

• 测试用例不超过 10 个。每个测试用例以整数 N 开头，表示该用例中的 ACM 粒子数量；
• 接下来 N 行，每行包含三个整数 x、y、r。其中 (x, y) 是二维图像中 ACM 粒子的位置，r 可为 0 或 1，分别代表亲水性或疏水性 ACM 粒子；
• x、y 的绝对值不超过 10000，N 不超过 1000；
• 输入以 N = 0 结束，无需处理该情况。

输出

对于每个测试用例，输出一行，包含一个整数，表示可溶解的 ACM 粒子的最大数量。

样例输入与输出

• 输入数据 1：

3
0 0 0
0 1 0
2 2 1
4
0 0 0
0 4 0
4 0 0
1 2 1
7
-1 0 0
1 2 1
2 3 0
2 1 1
0 3 1
1 4 0
-1 2 0
0

• 输出数据 1：

3
3
6

来源

上海 2004 年相关问题