**
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 ;
}
——既然選擇了遠方，便隻顧風雨兼程
歡迎各犇指正~