【BZOJ 3190】 3190: [JLOI2013]赛车 (半平面交)

3190: [JLOI2013]赛车

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

2016.1.17新加数据一组 By Nano_ape

Source

【分析】

　　时间作为x，路程作为y，有y=vx+st。

　　维护一个内部没有线的下凸壳即可。

实质上是简化版的半平面交，这题的直线有特殊形式，所以算起来更方便一些。

然后注意半平面交很重要的地方就是要学会特判去重，避免一些因为除以0 或者乘负数没变号的错误。

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<iostream>
 6 using namespace std;
 7 #define Maxn 10010
 8 
 9 struct node {double st,v;int id;}t[Maxn];
10 struct P {double x,y;};
11 
12 bool cmp(node x,node y) {return (x.v==y.v)?(x.st<y.st):(x.v<y.v);}
13 bool cmp2(int x,int y) {return t[x].id<t[y].id;}
14 
15 int ans[Maxn];
16 
17 P inter(int a,int b)
18 {
19     P x;
20     x.x=(t[b].st-t[a].st)/(t[a].v-t[b].v);
21     x.y=t[a].st+t[a].v*x.x;
22     return x;
23     // printf("= =%lf %lf
",x.x,x.y);
24 }
25 
26 bool jud(int a,int b,int c)
27 {
28     P x=inter(a,b);
29     // printf("= =%lf %lf
",x.y,x.x*t[c].v);
30     return (x.y-t[c].st)<x.x*t[c].v;
31 }
32 
33 int main()
34 {
35     int n;
36     scanf("%d",&n);
37     for(int i=1;i<=n;i++) scanf("%lf",&t[i].st);
38     for(int i=1;i<=n;i++) scanf("%lf",&t[i].v);
39     for(int i=1;i<=n;i++) t[i].id=i;
40     sort(t+1,t+1+n,cmp);
41     int cnt=1;
42     for(int i=2;i<=n;i++)
43     {
44         while(t[i].st>t[cnt].st&&cnt>0) cnt--;
45         t[++cnt]=t[i];
46     }
47     int tot=0;
48     if(cnt<=1)
49     {
50         printf("1
%d
",t[1].id);
51     }
52     else
53     {
54         ans[++tot]=1,ans[++tot]=2;
55         for(int i=3;i<=cnt;i++)
56         {
57             while(tot>=2&&jud(ans[tot],ans[tot-1],i)) tot--;
58             ans[++tot]=i;
59         }
60         sort(ans+1,ans+1+tot,cmp2);
61         printf("%d
",tot);
62         for(int i=1;i<tot;i++) printf("%d ",t[ans[i]].id);
63         printf("%d",t[ans[tot]].id);
64         printf("
");
65     }
66     return 0;
67 }

View Code

2016-12-25 16:05:00