题意：给了\(n\)个机器人的初始位置\(p\)和加速度\(a\)，起始速度都是\(0\)，问起跑后，问你有多少个机器人当过第一名，即在某一时刻，有唯一一个机器人如果冲在最前面则他是当过第一名的，注意并列第一则不算第一，赛道是无限长的。
大佬题解：here
AC_Code:
1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4 #include<cmath>
5 #include<map>
6 #include<iostream>
7 using namespace std;
8 typedef long long ll;
9 #define endl '\n'
10 const int maxn = 5e4+5;
11 const int inf = 0x3f3f3f3f;
12
13 struct node{
14 ll pi,ai;
15 }a[maxn],st[maxn],c[maxn];
16 //st为手写模拟栈
17
18 int n;
19 bool cmp(node x, node y){
20 if( x.ai==y.ai ) return x.pi>y.pi;
21 return x.ai>y.ai;
22 }
23
24 bool judge(node x, node y, node z){//判断方法就是求抛物线的交点
25 ll p1=2*(y.pi-x.pi);
26 ll a1=1*(x.ai-y.ai);
27 ll p2=2*(z.pi-y.pi);
28 ll a2=1*(y.ai-z.ai);
29 return p1*a2<=p2*a1;//p1/a1<=p2/a2
30 }
31
32 int main()
33 {
34 int T;
35 scanf("%d",&T);
36 while( T-- ){
37 map<ll, map<ll,ll> >mp;
38 scanf("%d",&n);
39 for(int i=1;i<=n;i++){
40 scanf("%lld%lld",&a[i].pi,&a[i].ai);
41 mp[a[i].pi][a[i].ai]++;
42 }
43 sort(a+1,a+1+n,cmp);
44
45 /****************************************/
46 //以下这一段是为了找可能在最前面的车,排除了一些不可能的车
47 //怎么排出的呢？
48 //我们首先是按照加速度从大到小排了序,如果加速度相同的话,那么按照初始位置从大到小排个序
49 //那么你加速度又小,初始位置也小的话,那就明显不可能冲到最前面了呀
50 //这一段我也是在比赛时想到了,然后后面就一直在想抛物线交点的问题,没有想到巧妙地运用栈,然后被交点问题越缠越乱也就没有想出来(太弱了......)
51 /***************************************/
52 int h=1;
53 st[h]=a[1];
54 ll mx=a[1].pi;
55 for(int i=2;i<=n;i++){
56 if( a[i].pi>mx ){
57 mx=a[i].pi;
58 st[++h]=a[i];
59 }
60 }
61
62 /***************************************/
63 //然后进行第二步排除:也就是根据谁先交,交谁来排除
64 //首先0位置在最前面的是一定可以冲在最前面的(也不一定哈,毕竟两人并列的不算,不过这个我们姑且认为他们就是第一,后面在删了他们就好了)
65 //注意这里我们按照加速度从小到大来了,这样好排除些(大佬的思路,我的脑子转不过来,没有想到......)
66 //用一个栈存取可能为第一名的机器人,如果栈中的机器人小于2个，就直接加入,因为只有两个人,加速度大的,在无限长的路上,最后一定会冲到前面
67 //否则如果第i个机器人超过次栈顶机器人的时间,小于等于栈顶机器人超过次栈顶机器人的时间,那么栈顶机器人其实是不会有机会单独冲到最前面的(如图1,2),这时我们就抛出栈顶,然后这样一直检验就好了
68 /***************************************/
69 int k=1;
70 c[1]=st[h];
71 for(int i=h-1;i>=1;i--){//倒着来,相当于按加速度从小到大排序了
72 if( k<=1 ){
73 c[++k]=st[i];
74 continue;
75 }
76 while( k>=2 ){
77 if( judge(st[i],c[k],c[k-1])) {
78 k--;
79 }else{
80 break;
81 }
82 }
83 c[++k]=st[i];
84 }
85
86 /************************************/
87 //终于到了最后一步排除了,排除并列的人
88 //上代码就直接理解了
89 /************************************/
90 int ans=0;
91 for(int i=1;i<=k;i++){
92 if( mp[c[i].pi][c[i].ai]==1 ){
93 ans++;
94 }
95 }
96 printf("%d\n",ans);
97 }
98 return 0;
99 }