bzoj3190【JLOI013】賽車
3190: [JLOI2013]賽車
Time Limit:10 SecMemory Limit:128 MB
Submit:1445Solved:454
[Submit][Status][Discuss]
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
計算幾何，維護一個y軸右面的半平面交。
注意兩個賽車速度和起始狀態都相同的情況。
#include
#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 10005
#define eps 1e-8
using namespace std;
int n,top,ans[maxn],f[maxn];
struct car{int p,v,id;}a[maxn],s[maxn];
vector v[maxn];
inline int read()
{
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;
}
inline bool cmp(car x,car y)
{
return (x.v==y.v)?x.p>y.p:x.v=2&&cross(s[top],s[top-1])>cross(s[top-1],a[i])) top--;
while (top>=1&&cross(s[top],a[i])<-eps) top--;
s[++top]=a[i];
}
F(i,1,top) ans[i]=s[i].id;
int tt=top;
F(i,1,tt) for(int j=0;j
