**
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
**
Source
**
当时觉得这个题可做……
本来的思路是按照k降序排序 不断维护最前面的车
wa了一次之后果断弃疗……代码打的好麻烦（不过还是深深的觉得自己的思路是没有错的……QAQ）
后来看到黄学长（orz HZWER）的博客里说按斜率（也就是v）排序 转化成了半平面交的问题（的确蛮裸的半平面交） 维护一个下凸的凸包
Code
（本蒟代码）
**
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
#define eps 1e-8
const int maxn=;
#define inf 2000000000
int n,top;
int ans[maxn];
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[maxn],q[maxn];
bool jud(car a,car b,car t){return inter(a,b)>inter(a,t);}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)scanf("%d",&c[i].p);
for(int i=;i<=n;i++)scanf("%d",&c[i].v);
for(int i=;i<=n;i++)c[i].id=i;
sort(c+,c++n);
top=;
for(int i=;i<=n;i++)
{
if(c[i].v!=c[i-].v||(c[i].v==c[i-].v&&c[i].p==c[i-].p))
top++;
c[top]=c[i];
}
n=top;top=;
for(int i=;i<=n;i++)
{
while(top>=&&inter(q[top],c[i])<-eps)top--;
while(top>=&&jud(q[top-1],q[top],c[i]))top--;
q[++top]=c[i];
ans[top]=c[i].id;
}
printf("%d\n",top);
sort(ans+,ans++top);
for(int i=;i<=top;i++)
{
printf("%d",ans[i]);
if(i!=top)printf(" ");
}
return ;
}
——既然选择了远方，便只顾风雨兼程
欢迎各犇指正~