BZOJ 3190 赛车
题面
这里有一辆赛车比赛正在进行，赛场上一共有N辆车，分别称为个g1，g2……gn。赛道是一条无限长的直线。最初，gi位于距离起跑线前进ki的位置。比赛开始后，车辆gi将会以vi单位每秒的恒定速度行驶。在这个比赛过程中，如果一辆赛车曾经处于领跑位置的话（即没有其他的赛车跑在他的前面），这辆赛车最后就可以得奖，而且比赛过程中不用担心相撞的问题。现在给出所有赛车的起始位置和速度，你的任务就是算出那些赛车将会得奖。
题解
这道题和BZOJ 1007 水平可见直线一样，只不过这次需要限定在第一象限内可见，所以当新直线和栈顶直线交点在y轴左侧，也要弹出栈顶直线。
注意一个坑：有重合直线。
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll N = 50005, INF = 0x3f3f3f3f;
ll n, top, idx, ans[N];
struct Line {
ll id, k, b;
bool operator < (const Line &obj) const{
return k != obj.k ? k < obj.k: b < obj.b;
}
} raw[N], line[N], stk[N];
int main(){
scanf("%lld", &n);
for(int i = 1; i <= n; i++)
raw[i].id = i, scanf("%lld", &raw[i].b);
for(int i = 1; i <= n; i++)
scanf("%lld", &raw[i].k);
sort(raw + 1, raw + n + 1);
line[idx = 1] = raw[1];
for(int i = 2; i <= n; i++)
line[(raw[i].k == raw[i - 1].k && raw[i].b != raw[i -1].b) ? idx: ++idx] = raw[i];
for(int i = 1; i <= idx; i++){
while(top && line[i].b > stk[top].b) top--;
while(top > 1 && (stk[top].b - line[i].b) * (stk[top].k - stk[top - 1].k)
< (stk[top - 1].b - stk[top].b) * (line[i].k - stk[top].k)) top--;
stk[++top] = line[i];
}
for(int i = 1; i <= top; i++) ans[i] = stk[i].id;
sort(ans + 1, ans + top + 1);
printf("%lld
", top);
for(int i = 1; i <= top; i++)
printf("%lld%c", ans[i], "
"[i == top]);
return 0;
}