http://acm.hdu.edu.cn/showproblem.php?pid=6759

Title:

There are n robots, each robot has an initial position and acceleration, and moves to the right at the same time, the runway is long and has no end point. At a given time, if the robot is the far right and the only one, then it is the leading robot at that time. Q: The number of leading robots.

answer:

Reference blog: https://blog.csdn.net/qq_44828887/article/details/107499606

The acceleration is sorted from small to large, and the position of the same acceleration is sorted from small to large. The robot behind can definitely surpass the robot in front (with the same acceleration, except for the same position);

Maintain a stack, the robot in the stack is the leading robot, and the robot currently in the stack can definitely surpass the robot in the stack.

When the position of the robot behind (to be pushed into the stack) is greater than or equal to the position of the robot in front (in the stack), the robot with the larger position will definitely surpass the robot in the previous (in the stack), the previous robot cannot be the leading robot, and the positions are equal and Robots with the same acceleration cannot be the leading robots in parallel, so they pop out of the stack;

When the robot in the stack >1, if the time when the two robots at the top of the stack meet is greater than the time when the robot at the top of the stack meets the robot about to enter the stack, the robot at the top of the stack will exit the stack;

Finally, determine whether there are parallel robots in the stack, and subtract them if there are.

Code:

#include <bits/stdc++.h>
using namespace std;
const int MAXN=5e4+5;
const int SIZE=5e4+5;
const long long mod=998244353;
typedef long long ll;
//typedef __int128 LL;
const int inf=0x3f3f3f3f;
const long long INF=0x3f3f3f3f3f3f3f3f;
int st[MAXN];
struct node
{
    ll l,a;
    bool operator<(const node &Node)const{
        if(a==Node.a)return l<Node.l;
        return a<Node.a;
    }
};
node p[MAXN];
map<node,int>mp;
bool check(node x,node y,node z)
{
    return (y.l-z.l)*(y.a-x.a)-(x.l-y.l)*(z.a-y.a)<=0;
}
int main()
{

    int t;
    scanf("%d",&t);
    while(t--)
    {
        mp.clear();
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%lld%lld",&p[i].l,&p[i].a);
            mp[p[i]]++;
        }

        sort(p+1,p+1+n);

        int top=0;
        for(int i=1;i<=n;i++)
        {
            while((top>0&&p[i].l>=p[st[top]].l)||(top>1&&check(p[st[top-1]],p[st[top]],p[i])))--top;
            st[++top]=i;
        }
        int ans=top;
        for(int i=1;i<=top;i++)
        {
            if(mp[p[st[i]]]>1)ans--;
        }
        printf("%d\n",ans);
    }
    return 0;
}