bzoj 3190: [JLOI2013]赛车 （半平面交）

Description

Input

Output

Sample Input

Sample Output

HINT

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

2016.1.17新加数据一组 By Nano_ape

Source

题解：半平面交

其实这道题跟bzoj1007水平可见直线是基本上相同的。

有些细节需要注意，在计算的过程中可能会炸int。

如果好几条直线相交于一点，那么这些直线都要输出。

如果存在重合的直线，那么这些直线都要输出。

#include<iostream>#include<cstring>#include<cmath>#include<cstdio>#include<algorithm>#define N 10003#define inf 1000000000#define LL long long using namespace std;struct data{	double k,b; int id;}a[N];bool Operator <(data a,data b) {	return a.k>b.k||a.k==b.k&&a.b<b.b;}int n,cnt,mark[N],q[N],ans[N];bool pd(data x1,data x2,data x3){	LL r1=(LL)(x3.k-x2.k)*(LL)(x2.b-x1.b);	LL r2=(LL)(x1.k-x2.k)*(LL)(x2.b-x3.b);	return r1>r2;}int main(){	freopen("race12.in","r",stdin);	freopen("my.out","w",stdout);	scanf("%d",&n);	for (int i=1;i<=n;i++) scanf("%lf",&a[i].b);	for (int i=1;i<=n;i++) scanf("%lf",&a[i].k),a[i].id=i;	a[0].k=-inf; a[0].b=0;	sort(a,a+n+1);	//for (int i=0;i<=n;i++) cout<<a[i].id<<" ";	//cout<<endl;	int head=0,tail=0;	for (int i=0;i<=n;i++) {		while (tail>0&&(pd(a[q[tail-1]],a[q[tail]],a[i])||a[i].k==a[q[tail]].k&&a[i].b>a[q[tail]].b)) 		 mark[a[q[tail]].id]=0,tail--;		if (a[i].k<a[q[tail]].k&&a[i].b<a[q[tail]].b) continue;		q[++tail]=i; mark[a[q[tail]].id]=1;	}	//for (int i=1;i<=n;i++) cout<<mark[i]<<" ";	//cout<<endl;	cnt=0;	for (int i=1;i<=n;i++) 	 if (mark[i]) ans[++cnt]=i;	PRintf("%d/n",cnt);	for (int i=1;i<=cnt-1;i++) printf("%d ",ans[i]);	printf("%d/n",ans[cnt]);}