Description

这里有一辆赛车比赛正在进行, 赛场上一共有 \(n\) 辆车, 分别称为个 \(g_1, g_2, \ldots g_n\). 赛道是一条无限长的直线. 最初,\(g_i\) 位于距离起跑线前进 \(k_i\) 的位置. 比赛开始后, 车辆 \(g_i\) 将会以 \(v_i\) 单位每秒的恒定速度行驶. 在这个比赛过程中, 如果一辆赛车 曾经处于领跑位置的话 (即没有其他的赛车跑在他的前面), 这辆赛车最后就可以得奖, 而且比赛过程中不用担心相撞的问题. 现在给出所有赛车的起始位置和速度, 你的任务就是 算出那些赛车将会得奖.

Input

第一行有一个正整数 \(n\) 表示赛车的个数.

接下来一行给出 \(n\) 个整数, 按顺序给出 \(n\) 辆赛车的起始位置.

再接下来一行给出 \(n\) 个整数, 按顺序给出 \(n\) 辆赛车的恒定速度.

Output

输出包括两行, 第一行为获奖的赛车个数.

第二行按从小到大的顺序输出获奖赛车的编号, 编号之间用空格隔开, 注意最后一个编号 后面不要加空格.

Sample Input

4
1 1 0 0
15 16 10 20

Sample Output

3
1 2 4

Data Range

对于 100% 的数据, 满足:\(n \leq 10000, 0 \leq k_i \leq 10^9, 0 \leq v_i \leq 10^9\)

Explanation

将一个车的一维运动加上时间轴变成静态的二维运动, 然后只需要求一下半平面交就可以了.

其实还是很好写的~

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long lli;
typedef long double llf;
const int maxn = 10010;
const int epsilon = 1e-3;

struct coord { llf k, b; int id; };
bool operator < (coord a, coord b) {
    if (a.k != b.k) return a.k < b.k;
    return a.b < b.b; }
llf intersect(coord a, coord b) { // Returns x axis.
    return (a.b - b.b) / (b.k - a.k); }
bool covered(coord a, coord x, coord y) { // a is covered by x and y
    return intersect(a, x) > intersect(x, y); }

int n, res[maxn];
coord car[maxn], que[maxn];

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%Lf", &car[i].b);
    for (int i = 1; i <= n; i++)
        scanf("%Lf", &car[i].k);
    for (int i = 1; i <= n; i++)
        car[i].id = i;
    sort(car + 1, car + 1 + n);
    // Remove duplicate trajectories
    int d_top = 1;
    for (int i = 2; i <= n; i++) {
        if (car[i].k != car[i - 1].k || (car[i].k == car[i - 1].k &&
                car[i].b == car[i - 1].b))
            d_top += 1;
        car[d_top] = car[i];
    }
    n = d_top;
    // Resolving queue and retrieving convex
    int top = 0;
    que[++top] = car[1];
    res[top] = car[1].id;
    for (int i = 2; i <= n; i++) {
        // Eliminating inappropriate lines
        while (top >= 1 && intersect(que[top], car[i]) < -epsilon)
            top -= 1;
        while (top >= 2 && covered(que[top], que[top - 1], car[i]))
            top -= 1;
        // Pushing into result queue
        que[++top] = car[i];
        res[top] = car[i].id;
    }
    // Output result
    sort(res + 1, res + 1 + top);
    printf("%d\n", top);
    for (int i = 1; i <= top; i++)
        printf("%d%s", res[i], i < top ? " " : "");
    printf("\n");
    return 0;
}