bzoj 3190: [JLOI2013]赛车 — 半平面交
Contents
3190: [JLOI2013]赛车
Time Limit: 10 Sec Memory Limit: 128 MB
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
2016.1.17新加数据一组 By Nano_ape
Source
半平面交入门题
就是判一下交点位置就好了
#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define inf 1000000007
#define ll long long
#define N 10010
inline int rd()
{
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 mp{int x,v,d;}a[N],q[N];
bool operator <(mp a,mp b){return a.v==b.v?a.x<b.x:a.v<b.v;}
int n,ans[N],tot;
inline double cck(mp a,mp b){return (a.x-b.x)*1.0/(b.v-a.v);}
inline bool ck(mp a,mp b,mp c){return cck(a,b)>cck(a,c);}
int main()
{
n=rd();
for(int i=1;i<=n;i++) a[i].x=rd();
for(int i=1;i<=n;i++) a[i].v=rd();
for(int i=1;i<=n;i++) a[i].d=i;
sort(a+1,a+n+1);tot=1;
for(int i=2;i<=n;i++)
{
if(a[i].v!=a[i-1].v||(a[i].v==a[i-1].v&&a[i].x==a[i-1].x)) tot++;
a[tot]=a[i];
}
n=tot;tot=0;
for(int i=1;i<=n;i++)
{
while(tot&&q[tot].x<a[i].x) tot--;
while(tot>1&&ck(q[tot-1],q[tot],a[i])) tot--;
q[++tot]=a[i];
ans[tot]=a[i].d;
}
printf("%d\n",tot);
sort(ans+1,ans+tot+1);
for(int i=1;i<=tot;i++) printf("%d%c",ans[i]," \n"[i==tot]);
return 0;
}
发表评论