我们可以将每一辆赛车看成一条直线,斜率为速度,纵截距为初始位置,那么问题就转化为求这n条直线处于最上面的直线。最上面是指在坐标系中,假设从x轴向下看,能看到的直线,只露一个点也算能看见。那么就类似水平可见直线这道题了。先按照斜率排序,然后维护直线的栈就行了。
/**************************************************************
Problem: 3190
User: BLADEVIL
Language: Pascal
Result: Accepted
Time:84 ms
Memory:548 kb
****************************************************************/
//By BLADEVIL
var
n :longint;
a, b, num :array[0..10010] of longint;
quea, queb :array[0..10010] of longint;
tot :longint;
quex :array[0..10010] of double;
ans :array[0..10010] of longint;
i, j :longint;
flag :array[0..10010] of boolean;
maxi :longint;
procedure swap(var a,b:longint);
var
c :longint;
begin
c:=a; a:=b; b:=c;
end;
procedure qs(low,high:longint);
var
i, j, xx, yy :longint;
begin
i:=low; j:=high; xx:=a[(i+j) div 2];
yy:=b[(i+j) div 2];
while ido
begin
while (a[i]or (a[i]=xx) and (b[i]>yy) do inc(i);
while (a[j]>xx) or (a[j]=xx) and (b[j]do dec(j);
if i<=j then
begin
swap(a[i],a[j]);
swap(b[i],b[j]);
swap(num[i],num[j]);
inc(i); dec(j);
end;
end;
if ithen qs(i,high);
if j>low then qs(low,j);
end;
procedure insert(i:longint);
var
k :longint;
x :double;
begin
if a[i]=quea[tot] then exit;
if tot>1 then
begin
x:=(queb[tot-1]-b[i])/(a[i]-quea[tot-1]);
while (tot>1) and (xdo
begin
dec(tot);
x:=(queb[tot-1]-b[i])/(a[i]-quea[tot-1]);
end;
end;
inc(tot);
quea[tot]:=a[i];
queb[tot]:=b[i];
quex[tot]:=(queb[tot-1]-b[i])/(a[i]-quea[tot-1]);
ans[tot]:=num[i];
end;
begin
read(n);
for i:=1 to n do read(b[i]);
for i:=1 to n do read(a[i]);
maxi:=0;
for i:=1 to n do if b[i]>b[maxi] then maxi:=i;
flag[maxi]:=true;
for i:=1 to n do if b[i]=b[maxi] then flag[i]:=true;
for i:=1 to n do num[i]:=i;
qs(1,n);
quea[1]:=a[1]; queb[1]:=b[1];
quex[1]:=-maxlongint; ans[1]:=num[1];
tot:=1;
for i:=2 to n do insert(i);
for i:=1 to tot do if quex[i]>=0 then break;
for j:=i to tot do flag[ans[j]]:=true;
qs(1,n);
for i:=1 to n do
if flag[i] then
begin
j:=i-1;
while (a[j]=a[i]) and (b[j]=b[i]) do
begin
flag[j]:=true;
dec(j);
end;
j:=i+1;
while (a[j]=a[i]) and (b[j]=b[i]) do
begin
flag[j]:=true;
inc(j);
end;
end;
tot:=0;
for i:=1 to n do if flag[i] then inc(tot);
writeln(tot);
for i:=1 to n do if flag[i] then break;
write(i);
for j:=i+1 to n do if flag[j] then write(‘ ‘,j);
writeln;
end.