把直线\(y=kx + b\)看成点\((k, b)\)，然后一条直线有贡献当且仅当它在凸包上，和斜率优化思想类似

#include 
    
     #include 
     
      #include 
      
       #include 
       
         const int MAXN = 50010;typedef long long LL;struct Point {    int x, y, idx;    explicit Point(int a = 0, int b = 0) { x = a, y = b; }    inline bool operator < (const Point & b) const {        return x == b.x ? y > b.y : x < b.x;    }    inline Point operator - (const Point & b) const {        return Point(x - b.x, y - b.y);    }} ps[MAXN];LL cross(const Point & a, const Point & b) {    return static_cast
        
          (a.x) * b.y - static_cast
         
           (a.y) * b.x;}int n, hav[MAXN];int st[MAXN], top;void solve() { std::sort(ps + 1, ps + 1 + n); st[1] = 1; st[top = 2] = 2; for (int i = 3; i <= n; ++i) { while (top >= 2 && cross(ps[st[top]] - ps[st[top - 1]], ps[i] - ps[st[top]]) >= 0) --top; st[++top] = i; } for (int i = 1; i <= top; ++i) hav[ps[st[i]].idx] = true;}int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d%d", &ps[i].x, &ps[i].y), ps[i].idx = i; solve();// for (int i = 1; i <= n; ++i) ps[i].x = -ps[i].x;// solve(); for (int i = 1; i <= n; ++i) if (hav[i]) printf("%d ", i); putchar(10); return 0;}