赛车问题

解题思路：

本题要求有哪些赛车在比赛的过程中当过第一名。

对于第 $i$ 辆赛车，它在 $t$ 时刻距离起跑线的距离 $S_i=k_i+v_it$，如果第 $i$ 辆赛车当过第一名，就意味着在某一个时刻 $t$ 时，$S_i$ 是所有赛车中的最大值。

如果将 $S_i$ 看作一个关于 $t$ 的函数，则所有的函数 $S_i$ 都是在直角坐标系上的一条截距 $>0$ 的直线。

可以任意在坐标系上画一些直线，然后观察，可以发现任意时刻在最上方的直线都当过第一名，可以发现这些最上方的部分其实就是所有直线的最上方的边界线。如果将所有直线都看成从左向右的有向直线，那么最上方的边界线包括的部分其实就是所有直线的左侧部分的交集，也就是所有直线的半平面交。因此最上方的边界线其实就是所有直线的半平面交的轮廓线。

因此我们接下来就是要对所有直线求一个半平面交，然后看一下哪些直线在半平面交上，注意，我们这里求的半平面交一定要在坐标系的第一象限上，因此我们可以加一个在 $y$ 轴上的从上往下的直线，再加一个在 $x$ 轴上的从左往右的直线，这样就能保证我们求的半平面交一定在第一象限。

注意，本题可能存在完全相同的直线，而我们这里是要将半平面交上所有的直线都求出来的，因此如果有完全相同的直线我们也是要考虑的，但是如果存在相同直线的话求半平面交的时候并不是那么好求，因此我们可以先将所有直线判个重，记录一下每条直线上有哪些赛车即可。

然后本题还可能存在多条直线交在一点的情况，如果这个点在半平面交上，那么经过这个点的所有直线我们也都要存下来，因此我们在维护单调队列的时候，只有交点在直线右侧时才将队头或队尾的直线删掉，如果交点在直线上，我们也要将直线保留。

另外还有一个非常恶心的点，本题的精度要求非常高，存的时候要用 $long~double$ 来存所有数据，并且精度限制要开到 $10^{-18}$

关于半平面交可以参考 半平面交的相关概念

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>

#define x first
#define y second

using namespace std;

typedef long double LD;
typedef pair<LD, LD> PDD;
typedef pair<int, int> PII;

const int N = 10010;
const LD eps = 1e-18;

struct Line
{
    PDD st, ed; //记录当前直线的起点和终点
    vector<int> ids; //存储当前直线上的所有赛车编号
}line[N]; //存储所有直线

int n, cnt;
int q[N]; //双端队列
int ki[N], vi[N]; //存储每个赛车的起点、速度
int res[N]; //存储所有当过第一名的车

PDD operator-(PDD a, PDD b) //重载减号运算符
{
    return {a.x - b.x, a.y - b.y};
}

int sign(LD x) //符号函数
{
    if(fabs(x) < eps) return 0;
    if(x < 0) return -1;
    return 1;
}

int dcmp(LD x, LD y) //比较 x 和 y 的大小
{
    if(fabs(x - y) < eps) return 0;
    if(x < y) return -1;
    return 1;
}

LD cross(PDD a, PDD b) //计算 a 和 b 的叉积
{
    return a.x * b.y - a.y * b.x;
}

LD area(PDD a, PDD b, PDD c) //计算 ab 和 ac 构成的平行四边形的有向面积
{
    return cross(b - a, c - a);
}

LD get_angle(const Line &a) //求直线 a 的角度
{
    return atan2(a.ed.y - a.st.y, a.ed.x - a.st.x);
}

bool cmp(const Line &a, const Line &b) //比较函数：将直线按照角度从小到大排序
{
    LD A = get_angle(a), B = get_angle(b);
    if(!dcmp(A, B)) return area(a.st, a.ed, b.ed) < 0; //如果角度相同，则让靠左的在前面
    return A < B;
}

PDD get_line_intersection(PDD p, PDD v, PDD q, PDD w) //求两个点向式直线的交点
{
    PDD u = p - q;
    LD t = cross(w, u) / cross(v, w);
    return {p.x + v.x * t, p.y + v.y * t};
}

PDD get_line_intersection(Line &a, Line &b) //求直线 a 和直线 b 的交点
{
    return get_line_intersection(a.st, a.ed - a.st, b.st, b.ed - b.st);
}

bool on_right(Line &a, Line &b, Line &c) //判断 bc 的交点是否在 a 的右侧
{
    PDD o = get_line_intersection(b, c);
    return sign(area(a.st, a.ed, o)) < 0;
}

void half_plane_intersection()
{
    sort(line, line + cnt, cmp); //将所有直线按照角度从小到大排序

    int hh = 0, tt = -1;
    for(int i = 0; i < cnt; i++)
    {
        if(i && !dcmp(get_angle(line[i]), get_angle(line[i - 1]))) continue; //方向相同的直线只考虑第一个
        while(hh + 1 <= tt && on_right(line[i], line[q[tt - 1]], line[q[tt]])) tt--; //删除队尾无用元素
        while(hh + 1 <= tt && on_right(line[i], line[q[hh]], line[q[hh + 1]])) hh++; //删除队头无用元素
        q[++tt] = i;
    }
    while(hh + 1 <= tt && on_right(line[q[hh]], line[q[tt - 1]], line[q[tt]])) tt--; //用队头更新队尾
    while(hh + 1 <= tt && on_right(line[q[tt]], line[q[hh]], line[q[hh + 1]])) hh++; //用队尾更新队头

    //找出所有当过第一的赛车
    int k = 0;
    for(int i = hh; i <= tt; i++)
        for(auto id : line[q[i]].ids)
            res[k++] = id;

    //将赛车编号排序并输出
    sort(res, res + k);
    printf("%d\n", k);
    for(int i = 0; i < k; i++) printf("%d ", res[i]);
}

int main()
{
    map<PII, vector<int>> ids; //存储所有直线
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &ki[i]);
    for(int i = 1; i <= n; i++) scanf("%d", &vi[i]);
    for(int i = 1; i <= n; i++)
        ids[{ki[i], vi[i]}].push_back(i);

    line[cnt++] = {{0, 10000}, {0, 0}}; //加一条 y 轴的边界
    line[cnt++] = {{0, 0}, {10000, 0}}; //加一条 x 轴的边界
    for(auto &[k, v] : ids) line[cnt++] = {{0, k.x}, {1, k.x + k.y}, v}; //加入所有直线

    half_plane_intersection();

    return 0;
}