传送门
题解：沙茶题
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define N 50010 using namespace std; int s[N],ans[N]; struct Line{ int k,b,id; Line operator=(const Line &L) { this->k=L.k;this->b=L.b; this->id=L.id;return *this; } }L[N]; inline bool cmp_by_kb(const Line &L1,const Line &L2) { if(L1.k==L2.k) return L1.b>L2.b; else return L1.k<L2.k; } inline double getInt(int u,int v) { double a1=L[u].k,b1=L[u].b; double a2=L[v].k,b2=L[v].b; return (b2-b1)/(a1-a2); } const double eps=0.00001; inline double gabs(double x) { return (x>0)?x:-x; } inline int dcmp(double x) { if(gabs(x)<eps) return 0; return (x>0)?1:-1; } int main() { int n;scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d",&L[i].k,&L[i].b); L[i].id=i; } sort(L+1,L+n+1,cmp_by_kb); // for(int i=1;i<=n;i++) cout<<L[i].id<<" "<<L[i].b<<endl; int cnt=0; for(int i=1;i<=n;i++) { L[++cnt]=L[i]; while(i<n&&L[cnt].k==L[i+1].k) i++; } n=cnt;int top=0; for(int i=1;i<=n;i++) { while(top>=2&&dcmp(getInt(s[top],i)-getInt(s[top-1],s[top]))<=0) top--; s[++top]=i; } n=top; for(int i=1;i<=n;i++) ans[i]=L[s[i]].id; sort(ans+1,ans+n+1); for(int i=1;i<=n;i++) printf("%d ",ans[i]); return 0; }