题目大意
有(n)个机器人，每个机器人有一个初始位置(p_i)和加速度(a_i)。在(t)时刻，该机器人的速度是(v_i(t)a_icdot t)。
现在所有机器人同时启动，请问无限长的时间之内，会有多少个机器人，至少在一个时刻“领先”？我们说一个机器人领先，是指在这个时刻，它的位置，严格大于其他所有机器人。
数据范围：(1leq nleq 50000)，(0leq p_i,a_ileq 2^{31})。
本题题解
物理学上有这样一个公式：
其中(p)是初始位置，(a)是加速度，(t)是时间，(s)是路程（也就是在(t)时刻的位置）。
利用这个公式，我们可以计算出，两个机器人(i,j)（假设(a_i>a_j), (p_i<p_j)），(i)何时会追上(j)。这相当于解这样一个关于(t)的方程：
可以解得：
回到本题。先将这些机器人，按加速度从小到大排序（加速度相同时按初始位置从小到大排）。然后依次考虑每个机器人，维护一个单调栈，栈里的机器人加速度递增，每一个机器人会在某一时刻超过前一个机器人，并成为领先者（因此他们的初始位置一定是递减的）。
对于当前机器人，栈里的其他机器人，加速度一定小于等于它。拿当前机器人(i)和栈顶的机器人(j)比较（(a_igeq a_j)）：
- 如果(p_igeq p_j)，则(j)永远也无法领先了，将其出栈。
- 否则，如果(p_i<p_j)（此时一定有(a_i>a_j)，因为(a)相同的机器人是按位置从小到大排序的），那(i)一定会在某个时刻追上(j)。这个时刻可以用我们上述的方程解出来，不妨记为(t_1)。此时，如果栈里有(geq 2)元素，考虑(j)前面的那个机器人(k)，计算出(j)追上(k)的时刻，不妨记为(t_2)。如果(t_2geq t_1)，说明(j)永远不可能领先了，将其出栈。
如此重复，直到栈顶的元素(j)，不满足上述两条，说明我们已经排除了所有“在(i)加入后，不可能再领先的机器人”。此时再将(i)入栈即可。
值得一提的是，判断(t_2geq t_1)时，不需要真的开根号、解出来。只需要移项，转化为乘法。这样可以避免精度误差。
时间复杂度(O(nlog n))。
后记：我们可以进一步思考一下这种做法的本质。其实是把(t^2)当成(x)，把(s)当成(y)，这样一个二次函数，就被转化为了一次函数。而一次函数上的这种追及问题，是很经典的：bzoj1007 水平可见的直线。
参考代码：
//problem:hdu6759
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mk make_pair
#define lob lower_bound
#define upb upper_bound
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T>inline void ckmax(T& x,T y){x=(y>x?y:x);}
template<typename T>inline void ckmin(T& x,T y){x=(y<x?y:x);}
const int MAXN=5e4;
int n;
struct Robot_t{
ll p,a;
}p[MAXN+5];
bool cmp(Robot_t lhs,Robot_t rhs){
//按加速度从小到大排,加速度相同按位置从小到大排
if(lhs.a == rhs.a)
return lhs.p < rhs.p;
return lhs.a < rhs.a;
}
bool check(const Robot_t& a,const Robot_t& b,const Robot_t& c){
assert(a.a < b.a && b.a < c.a);
// return b追上a的时间 >= c追上b的时间
return (b.p-a.p) * (b.a-c.a) - (c.p-b.p) * (a.a-b.a) >= 0;
}
int sta[MAXN+5],top;
void solve_case(){
cin>>n;
map<pair<ll,ll>,int>mp;
for(int i=1;i<=n;++i){
cin>>p[i].p>>p[i].a;
mp[mk(p[i].p,p[i].a)]++;
}
sort(p+1,p+n+1,cmp);
top=0;
for(int i=1;i<=n;++i){
while(top){
if(p[sta[top]].p <= p[i].p)
--top;
else if(top>1 && check(p[sta[top-1]],p[sta[top]],p[i]))
--top;
else break;
}
sta[++top] = i;
}
int ans=top;
for(int i=1;i<=top;++i){
if(mp[mk(p[sta[i]].p,p[sta[i]].a)] > 1)
ans--;
}
cout<<ans<<endl;
}
int main() {
int T;cin>>T;while(T--){
solve_case();
}
return 0;
}