求助!!!
查看原帖
求助!!!
519573
Daniel_yao楼主2022/6/24 23:21
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
struct Node{
  int id, k, b;
}a[N];
int n, top, ans[N], stk[N];
bool cmp(Node x, Node y){
  if(x.k != y.k) return x.k > y.k;
  else return x.b > y.b;
}

double c(int x, int y){
  return ((1.0 * (a[x].b - a[y].b)) / (a[y].k - a[x].k));
}

int main(){
  cin >> n;
  for(int i = 1;i <= n;i++){
    cin >> a[i].k >> a[i].b;// 斜率与截距
    a[i].id = i;
  }
  sort(a + 1, a + n + 1, cmp);
  for(int i = 1;i <= n;i++){
    if(a[i].k == a[i-1].k && i > 1){
      continue;
    }
    while(top && c(stk[top], i) >= c(stk[top], stk[top-1])){
      top--;
    }
    stk[++top] = i;
    ans[top] = a[i].id;
  }
  sort(ans + 1, ans + top + 1);
  for(int i = 1;i <= top;i++){
    cout << ans[i] << " ";
  }
  return 0;
}

2022/6/24 23:21
加载中...