BZOJ 3190 赛车 | 计算几何

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\n", top);

    for(int i = 1; i <= top; i++)

	printf("%lld%c", ans[i], " \n"[i == top]);

    return 0;

}