Bzoj3190 [jloi2013]赛车

无脑半平面交

Posted by yjjr's blog on February 5, 2018

标签:半平面交

题目

题目传送门

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

分析

无脑题

横坐标按照时间排,纵坐标按路程排

然后维护x轴右半部分的半平面交即可

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define eps 1e-8
using namespace std;
inline ll read()
{
	ll 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;
}
const int maxn=1e5+6;
int n,top,ans[maxn];
struct node{
	int p,v,id;
	friend double Inter(node a,node b){return (double)(a.p-b.p)/(b.v-a.v);}
	friend bool operator<(node a,node b){return a.v!=b.v?a.v<b.v:a.p<b.p;}
}c[maxn],que[maxn];
inline bool jud(node a,node b,node t){return Inter(a,b)>Inter(a,t);}
int main()
{
	n=read();
	rep(i,1,n)c[i].p=read();
	rep(i,1,n)c[i].v=read();
	rep(i,1,n)c[i].id=i;
	sort(c+1,c+1+n);
	top=1;
	rep(i,2,n){
		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;
	que[++top]=c[1];ans[1]=c[1].id;
	rep(i,2,n){
		while(top>=1&&(Inter(que[top],c[i])<-eps))top--;
		while(top>=2&&jud(que[top-1],que[top],c[i]))top--;
		que[++top]=c[i],ans[top]=c[i].id;
	}
	cout<<top<<endl;
	sort(ans+1,ans+1+top);
	rep(i,1,top)printf("%d%c",ans[i],i!=top?' ':'\n');
	return 0;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr