题面
题解
我们可以尝试寻找临界值。枚举，那么令\(\frac{A}{a_i}+\frac{B}{b_i}=\frac{A}{a_j}+\frac{B}{b_j}\)，如果这对\(A,B\)在\(i,j\)取到最值，那么\(i,j\)有用。
将每个型号看成平面上的点\((\frac1{a_i},\frac1{b_i})\)，我们的问题变成了：给定任意\(A,B\)，最小化\(z=Ax+By\)（\(x,y\)即为点的坐标）。因为\(A,B\)为正实数,所以目标函数的斜率为负。于是，有用的点分布在该点集的左下凸包上。使用类似斜率优化的方法求出凸包即可。
时间复杂度\(O(nlogn)\)
#include<cstdio>
#include<cstring>
#include<algorithm>
#define RG register
#define clear(x, y) memset(x, y, sizeof(x));inline int read()
{int data = 0, w = 1;char ch = getchar();while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar();if(ch == '-') w = -1, ch = getchar();while(ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar();return data*w;
}const int maxn(3e5 + 10);
int q[maxn], top, next[maxn], ok[maxn], n;
struct point { int x, y, id; } p[maxn];
double k[maxn];
inline bool operator < (const point &lhs, const point &rhs)
{return lhs.x > rhs.x || (lhs.x == rhs.x && lhs.y > rhs.y);
}inline double slope(const point &i, const point &j)
{return 1. * i.x * j.x * (j.y - i.y) / (1. * i.y * j.y * (j.x - i.x));
}int main()
{n = read(); int minx, miny = 0;for(RG int i = 1; i <= n; i++){p[i] = (point) {read(), read(), i};if(miny < p[i].y || (miny == p[i].y && minx < p[i].x))minx = p[i].x, miny = p[i].y;}std::sort(p + 1, p + n + 1);q[top = 1] = 1;for(RG int i = 2; i <= n && minx <= p[i].x; i++){if(p[q[top]].x == p[i].x){if(p[q[top]].y == p[i].y)next[p[i].id] = next[p[q[top]].id], next[p[q[top]].id] = p[i].id;continue;}while(top > 1 && k[top] > slope(p[q[top]], p[i])) --top;q[++top] = i; k[top] = slope(p[q[top - 1]], p[i]);}for(RG int i = top; i; --i)for(RG int j = p[q[i]].id; j; j = next[j]) ok[j] = 1;for(RG int i = 1; i <= n; i++) if(ok[i]) printf("%d ", i);return 0;
}
