我们可以将每一辆赛车看成一条直线,斜率为速度,纵截距为初始位置,那么问题就转化为求这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 i<j do begin while (a[i]<xx) or (a[i]=xx) and (b[i]>yy) do inc(i); while (a[j]>xx) or (a[j]=xx) and (b[j]<yy) 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 i<high then 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 (x<quex[tot]) do 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.