【bzoj3190】[JLOI2013]赛车

2015.04.14 18:40 Tue | 1次阅读 | 旧日oi | 固定链接 | 源码

Description

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

Input

第一行有一个正整数N表示赛车的个数。
接下来一行给出N个整数,按顺序给出N辆赛车的起始位置。
再接下来一行给出N个整数,按顺序给出N辆赛车的恒定速度。

Output

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

Sample Input

4
1 1 0 0
15 16 10 20

Sample Output

3
1 2 4

HINT

对于100%的数据N<=10000, 0<=ki<=10^9, 0<=vi<=10^9

题解

这个题让我怀念起初二时刚学不久就去省选四个小时写第一题的时光……枚举t,写暴力……最后也不知道多少分……哎,时间真是都荒废掉了……
正解是半平面交,以每个人的位置为纵坐标,时间为横坐标建系,每条直线的斜率就是速度,然后搞出哪条线在半平面交上就可以了

我的程序

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<bitset>
#include<stack>
#include<ctime>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define maxn 100010
#define ll long long
#define mod 1000000007
#define inf 0x3f3f3f3f
#define eps 1e-11
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct car{
    int p,v,id;
}c[maxn],q[maxn];
bool cmp(const car &a,const car &b)
{
    if(a.v!=b.v) return a.v<b.v;
    return a.p<b.p;
}
double inter(const car &a,const car &b)
{
    return (double)(a.p-b.p)/(b.v-a.v);
}
bool jud(const car &a,const car &b,const car &c)
{
    return inter(a,b)>inter(a,c);
}
int n,ans[maxn];
int main()
{
    n=read();
    for(int i=1;i<=n;i++) c[i].p=read();
    for(int i=1;i<=n;i++) c[i].v=read();
    for(int i=1;i<=n;i++) c[i].id=i;
    sort(c+1,c+n+1,cmp);
    int top=1;
    for(int i=2;i<=n;i++)
    {
        if(c[i].v!=c[i-1].v||(c[i].v==c[i-1].v&&c[i].p==c[i-1].p)) top++;
        c[top]=c[i];
    }
    n=top;
    q[top=1]=c[1];ans[1]=c[1].id;
    for(int i=2;i<=n;i++)
    {
        while(top>=1&&inter(q[top],c[i])<-eps) top--;
        while(top>=2&&jud(q[top-1],q[top],c[i])) top--;
        q[++top]=c[i];ans[top]=c[i].id;
    }
    cout<<top<<endl;
    sort(ans+1,ans+top+1);
    for(int i=1;i<top;i++)
    printf("%d ",ans[i]);
    printf("%d\n",ans[top]);
}```