分析

题意：

桑迪喜欢玩机器人。他将组织一场机器人比赛。他将给获奖者一些礼物。机器人排成一行。它们具有其初始位置（与起始线的距离）和加速速度。这些值可能不同。比赛开始时，所有机器人都会向右移动：

在此，a是加速速度，t是从开始时刻起的时间。

现在的问题是，从一开始就可以领导多少个机器人？

这里的领导者是指从起跑线到现在的唯一最右边的机器人。也就是说，在某个特定时间，如果机器人是最右边且唯一的，那么它就是当时的领先机器人。可能有具有相同初始位置和相同加速速度的机器人。

跑道很长，您可以假设没有终点线。

输入项
输入包含几个测试用例。输入的第一行包含一个整数T（1≤T≤50），表示测试用例的数量。每个测试用例的第一行包含一个整数N（0 <N≤50000），表示机械手的数量。以下N条线中的每条线均由两个整数组成：p，a（0 <p，a <2^31）表示机器人的位置及其加速速度。

输出量
对于每个测试用例，在单独的行上输出可能的领先机器人的数量。

分析：

很自然的我们可以排除一些特殊情况：
1.如果有两个相同位置，相同加速度的机器人那么这两个机器人都不可能成为leader
2.如果对于机器人r在他前面有加速度比他大或者等于他的机器人那么他也不可能成为leader
3.如果对于机器人r在r所处的的位置上如果有加速度比他大的机器人那么他不可能成为leader

第一种机器人可能到达前方但是因为并列原因所以不可能成为leader要额外标记
第二、三种机器人永远不会到达前方所以直接去掉。

在进行了以上操作的基础上
下面，正式的判断：
首先我们很自然的想对机器人进行排序。按照x的顺序从大到小排序
那么对于ri我们很清楚：
如果我们知道他追上(r1,r2,r3,......,ri-1)所需时间的最大值为t1
(ri+1,ri+2,ri+3....rn)追上ri的最小值为t2
那么我们判断:
若t1<t2则ri可以成为leader
若t1>=t2则不可以成为leader

这是基本的想法
但是如果直接实施的话则为O(n^2)
我们需要尝试优化。
数据结构貌似不行，那么我们只能从其他的方向入手

我们维护一个栈[r1,r2,r3]
然后遍历机器人ri把他向栈里面塞。
如果栈顶的机器人rx他到最前面的时间小于等于ri追上他的时间，那么我们就把rx给pop掉
一直这样。直到栈顶的元素到前面的时间大于ri追上他的时间。
那会不会出现这样的情况[r1,r2,r3]现在我要塞r4
然后发现r3不满足条件不用pop那么我停下来塞r4
会不会r2却满足条件从而导致我漏掉了呢？
首先r2到前方的时间一定小于r3，否则在r3的时候就已经把r2给削除掉了
且r4追上r2的时间一定小于r4追上r3的时间。
因为上面说了r4追上r3时r3已经在最前面了，即r3已经超过r2了。
所以在r4追上r3之前一定时已经经过r2了。

因此只要这样做我们最后便可以得到正确答案。

那么问题的关键便是：如何得到rx到最前面的时间呢？
回到上述栈[r1,r2,r3,r4]
这里面肯定r4追上r3的时间一定大于r3到最前面的时间，那么我说r4到最前面的时间就是r4追上r3的时间
这是很重要的！！！！！！
假设r4追上r3的时间为t1，r3到达最前面的时间为t2。t1>t2
则经过了了t2时间后，r3已经到最前面了，并且因为r3的加速度都大于r1,r2的缘故所以接下来只会和r1,r2的距离越拉越远
所以t4追赶前方所有的机器人其实就是r4追赶r3！！
故，r4追赶r3所花费的时间就是r4到最前方所需要的时间。

关键思路已经解出来了
最后再遍历一下栈中的机器人判断一下他们是否是重复机器人就好了。

至此，我们全部分析完了。
排序复杂度O(NlogN),栈复杂度O(N)故总复杂度O(NlogN)

代码如下：

//陈业元，孙龙飞，孙孜斌
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int max_n = 100010;
struct rabt{
    int x;
    int a;
    bool can;
    bool operator<(const rabt& r1) { return x == r1.x ? a > r1.a : x > r1.x; }
    bool operator==(const rabt& r1) { return ((x == r1.x) && (a == r1.a)); }
    rabt() :x(0), a(0), can(1) {}
}rabts[max_n];
int t, n;

int main() {
    ios::sync_with_stdio(0);
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 0;i < n;i++)
            cin >> rabts[i].x >> rabts[i].a;
        sort(rabts, rabts + n);
        for (int i = 0; i < n - 1; i++) {
            rabts[i].can = rabts[i + 1].can = true;
            if (rabts[i] == rabts[i + 1])
                rabts[i].can = rabts[i + 1].can = false;
        }
        vector<rabt>tmp;
        for (int i = 0;i < n;i++)
            if (i == 0 || rabts[i].a > tmp.back().a)
                tmp.push_back(rabts[i]);
        n = tmp.size();
        if (n == 1) {
            if (tmp[0].can)cout << 1 << endl;
            else cout << 0 << endl;
            continue;
        }
        vector<rabt> stack;
        stack.push_back(tmp[0]);stack.push_back(tmp[1]);
        for (int i = 2;i < n;i++) {
            rabt cur = tmp[i];
            while (stack.size() >= 2) {
                rabt r1 = stack[stack.size() - 1];
                rabt r2 = stack[stack.size() - 2];
                if (((ll)r1.x - cur.x) * ((ll)r1.a - r2.a) > ((ll)r2.x - r1.x) * ((ll)cur.a - r1.a))break;
                else stack.pop_back();
            }stack.push_back(cur);
        }
        int ans = 0;
        for (int i = 0;i < stack.size();i++)
            if (stack[i].can)ans++;
        cout << ans << endl;
    }
}

不难，但逻辑绕人。