[Wf2016]Spin Doctor
时间限制：30s 空间限制：128MB
题目描述
大选要到了，受候选人X的要求，你调查了n个人，并记录了每个人的3个信息：
ai--他们能记忆π的多少位
bi--他们的头发数量
ci--他们是否会给候选人X投票
你需要找到某个公式使这些结果看起来有意义。你要选择2个实数S和T，将所有调查结果按ai*S+bi*T排序。如果ci
为true的人聚集在了一起，你会觉得这个排序看起来不错。更准确地说，如果j和k分别是第一个和最后一个ci为tr
ue的人的下标，你想要最小化k-j+1。注意有些S和T会让排序时出现相等的情况，这时你应该假设最坏情况发生，
即排序使得k-j+1最大。
输入格式
第一行一个数n(1 ≤ n ≤ 250000)为被调查的人数。
接下来每行描述一个人的ai(0 ≤ ai ≤ 2000000)、bi(0 ≤ bi ≤ 2000000)、ci
ci是一个0/1变量。保证至少有一个人投了X的票（即至少有一个ci为true）
输出格式
对于所有可能的实数对(S,T)，输出最小的k-j+1。
样例输入
100 7487 4751 1 7499 5064 1 7471 5376 1 7404 5683 1 7300 5979 1 7159 6260 1 6984 6520 1 6777 6757 1 6543 6966 1 6284 7144 1 6006 7288 1 5711 7396 1 5405 7466 1 5092 7498 1 4780 7490 1 4469 7442 1 4167 7357 1 3878 7234 1 3607 7075 1 3358 6884 1 3135 6664 1 2941 6417 1 2780 6147 1 2653 5860 1 2564 5559 1 2513 5249 1 2501 4936 1 2529 4624 1 2596 4317 1 2700 4021 1 2841 3740 1 3016 3480 1 3223 3243 1 3457 3034 1 3716 2856 1 3994 2712 1 4289 2604 1 4595 2534 1 4908 2502 1 5220 2510 1 5531 2558 1 5833 2643 1 6122 2766 1 6393 2925 1 6642 3116 1 6865 3336 1 7059 3583 1 7220 3853 1 7347 4140 1 7436 4441 1 4946 8828 0 8742 4313 0 2126 2132 0 9435 3372 0 5088 584 0 278 7609 0 464 5305 0 1577 509 0 2804 8754 0 9047 1580 0 1558 5541 0 3041 9135 0 7723 9004 0 3245 7600 0 3274 8477 0 7867 5690 0 4184 9319 0 8425 475 0 942 6676 0 8254 1405 0 7168 6512 0 2541 51 0 3017 7811 0 6805 39 0 4351 8732 0 533 9472 0 1513 9570 0 634 790 0 5809 9609 0 6536 8399 0 5640 9504 0 2408 9157 0 1271 1853 0 1976 2706 0 9332 7001 0 1048 3322 0 9764 9397 0 1901 1449 0 3985 2122 0 7139 9767 0 5835 8305 0 746 585 0 3025 8187 0 2301 782 0 9741 3033 0 3960 8756 0 693 3827 0 1169 7143 0 556 8694 0 3721 1983 0
样例输出
61
提示
没有写明提示
题目来源
鸣谢Shimakaze提供译文