[BZOJ3190]&&[JLOI2013] 赛车

描述 Description

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

输入格式 InputFormat

第一行有一个正整数 N 表示赛车的个数。

接下来一行给出 N 个整数,按顺序给出 N 辆赛车的起始位置。

再接下来一行给出 N 个整数,按顺序给出 N 辆赛车的恒定速度。

输出格式 OutputFormat

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

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

样例输入 SampleInput

4
1 1 0 0
15 16 10 20

样例输出 SampleOutput

3
1 2 4


BZOJ 3190


类似水平可见直线,不过有可能存在完全重合的两条直线必须都保留,而且为了保证只有第一象限可见,引入直线 y=(max{k})x。

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
const int maxn=10005;
int i,j,t,n,m,l,r,k,z,y,x;
struct car
{
    int k,v,id;
    bool operator > (const car& tmp) const
        {
            return (v==tmp.v)?(k>tmp.k):(v<tmp.v);
        }
    bool operator < (const car& tmp) const
        {
            return (id<tmp.id);
        }
}a[maxn];
inline double crossx(car a,car b)
{
    return (double)((double)a.k-b.k)/(double)(b.v-a.v);
}
vector <car> s;
int main()
{
    scanf("%d",&n);
    for (t=0,i=1;i<=n;i++) scanf("%d",&a[i].k),t=max(t,a[i].k);
    for (i=1;i<=n;i++) scanf("%d",&a[i].v),a[i].id=i;
    n++;
    a[n]=(car){t,0,n};
    sort(a+1,a+n+1,greater<car>());
    s.clear();
    for (i=1;i<=n;i++)
    {
        if (!s.empty() && a[i].v==s.back().v)
        {
            if (a[i].k==s.back().k) s.push_back(a[i]);
        }
        else
        {
            while (s.size()>1 && crossx(a[i],s.back())<crossx(s.back(),s[s.size()-2])) s.pop_back();
            s.push_back(a[i]);
        }
    }
    sort(s.begin(),s.end());
    s.pop_back();
    printf("%d\n",(int)s.size());
    for (i=0;i<s.size()-1;i++) printf("%d",s[i].id);
    printf("%d\n",s[s.size()-1].id);
    return 0;
}