贪心+思维

这一题我本来也是可以做的
经过一段时间的思考后我们可以发现，最先撞击的两个无人机一定是相邻的两个无人机

我们可以用一个优先队列维护所有的相邻的两点撞击的时间
然后贪心地取撞击时间小的点，然后更新

这个撞击时间是一个小数，在比较时有精度误差，因为精度误差我一直错

在涉及小数比较的时候，优先考虑是否可以进行ll比较，避免除法，转化为乘法

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int max_n = 1e5+100;
const double inf = 1e18;
int n;
pll ns[max_n];
int lft[max_n],rgt[max_n];
int tot=0;
struct node
{
    ll x,v;
    int l,r;
    node(ll xx,ll vv,int lf,int rr)
    {
        x=xx;v=vv;l=lf;r=rr;
    }
    bool operator<(const node& nn)const
    {
        bool ans;
        if (v<=0&&nn.v<=0)ans= l<nn.l;
        else if (v<=0)ans= false;
        else if (nn.v<=0)ans=true;
        else
        {
            ans=x*nn.v<nn.x*v;
        }
        return !ans;
    }
};

bool used[max_n];
int main()
{
    ios::sync_with_stdio(0);
    cin>>n;
    ++tot;
    for (int i=1;i<=n;++i)
    {
        cin>>ns[i].first>>ns[i].second;
    }
    for (int i=1;i<=n;++i)rgt[i]=i+1;
    for (int i=1;i<=n;++i)lft[i]=i-1;
    priority_queue<node> que;
    for (int i=2;i<=n;++i)que.push(node(ns[i].first-ns[i-1].first,ns[i-1].second-ns[i].second,i-1,i));
    while (!que.empty())
    {
        node nn = que.top();
        que.pop();
        if (nn.v<=0)break;
        int lt = nn.l,rt = nn.r;

        if (used[lt]||used[rt])continue;
        int L = lft[lt],R = rgt[rt];
        used[lt]=used[rt]=1;
        if (L!=0&&R!=n+1)
        {
            que.push(node(ns[R].first-ns[L].first,ns[L].second-ns[R].second,L,R));
        }
        rgt[L]=R;
        lft[R]=L;
    }
    int ans=0;
    for (int i=1;i<=n;++i)
    {
        if (!used[i])++ans;
    }
    cout<<ans<<endl;
    for (int i=1;i<=n;++i)if (!used[i])cout<<i<<" ";cout<<endl;

}