「BZOJ3190」[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
1 1 0 0
15 16 10 20
Sample Output
3
1 2 4
1 2 4
HINT
对于100%的数据N<=10000, 0<=ki<=10^9, 0<=vi<=10^9
题解
横坐标时间，纵坐标路程
按照斜率排序后维护x轴右半部分的半平面交即可。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
#include<cstdio> #include<cmath> #include<ctime> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #include<set> #define ll long long #define eps 1e-8 #define mod 1000000007 #define inf 2000000000 using namespace std; int read() { int f=1,x=0;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; } int n,top; int ans[10005]; struct car{ int p,v,id; friend bool operator<(car a,car b){ if(a.v!=b.v)return a.v<b.v; return a.p<b.p; } friend double inter(car a,car b){ return (double)(a.p-b.p)/(b.v-a.v); } }c[10005],q[10005]; bool jud(car a,car b,car t) { return inter(a,b)>inter(a,t); } 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); 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;top=0; q[++top]=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; } printf("%d\n",top); sort(ans+1,ans+top+1); for(int i=1;i<=top;i++) { printf("%d",ans[i]); if(i!=top)printf(" "); } return 0; } |
计数器 9855471
OI 课件=>
OI 课件=>
4
0 1 1 5
10 9 9 7
Hack!
直接暴力半平面交即可
你看我写的不伦不类2333