Tavas is a cheerleader in the new sports competition named "Pashmaks".
This competition consists of two part: swimming and then running. People will immediately start running R meters after they finished swimming exactly S meters. A winner is a such person that nobody else finishes running before him/her (there may be more than one winner).
Before the match starts, Tavas knows that there are n competitors registered for the match. Also, he knows that i-th person's swimming speed is si meters per second and his/her running speed is ri meters per second. Unfortunately, he doesn't know the values of R and S, but he knows that they are real numbers greater than 0.
As a cheerleader, Tavas wants to know who to cheer up. So, he wants to know all people that might win. We consider a competitor might win if and only if there are some values of R and S such that with these values, (s)he will be a winner.
Tavas isn't really familiar with programming, so he asked you to help him.
The first line of input contains a single integer n (1 ≤ n ≤ 2 × 105).
The next n lines contain the details of competitors. i-th line contains two integers si and ri (1 ≤ si, ri ≤ 104).
In the first and the only line of output, print a sequence of numbers of possible winners in increasing order.
3
1 3
2 2
3 1
1 2 3
3
1 2
1 1
2 1
1 3 题意：n个人比赛，游泳和赛跑，游泳距离S，赛跑R。 每个人对应两个速度（陆地和水上的）， 如果存在 S ， R，使得第i个人胜利，那么输出i。
题目要求 ：输出所有的i。
可以把 ri si的倒数看成坐标系上的点，时间可以当做 两个向量的点积也就是投影。。。
求出凸包。 p1 为最下面的点如果有多个选取最左面的那个， p2位最左面的点如果有多个选取最下面的那个。 那么凸包上从p1到p2的点必然满足题意。注意判重
#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-;
const int inf = 0x3f3f3f3f;
struct Point
{
double x, y;
int idx;
Point (double x = , double y = ):
x(x), y(y) {}
bool operator == (const Point &rhs)const
{
return abs(x - rhs.x) < eps && (y - rhs.y) < eps;
}
bool operator < (const Point &rhs) const
{
return x < rhs.x || (abs(x-rhs.x) < eps && y < rhs. y);
}
};
typedef Point Vector;
Vector operator - (Point p1, Point p2)
{
return Vector (p1.x-p2.x, p1.y-p2.y);
}
double Cross(Vector p1, Vector p2)
{
return p1.x*p2.y - p2.x*p1.y;
}
Point p[], cvx[];
bool ans[];
int pos[];
bool cmp(double x)
{
return x < || abs(x) < eps;
}
int ConvexHull(int n)
{
sort (p, p+n);
// n = unique(p, p+n) - p;
int tot = ;
for (int i = ; i < n; i++)
{
if (i > && p[i] == p[i-])
{
pos[i] = pos[i-];
continue;
}
pos[i] = i;
while (tot > && cmp(Cross(cvx[tot-]-cvx[tot-], p[i]-cvx[tot-])) == true)
tot--;
cvx[tot++] = p[i];
}
int k = tot;
for (int i = n-; i >= ; i--)
{
while (tot > k && cmp(Cross(cvx[tot-]-cvx[tot-],p[i]-cvx[tot-]) == true))
tot--;
cvx[tot++] = p[i];
}
if (n > )
tot--;
return tot;
}
bool cmp2(const Point &p1, const Point &p2)
{
return p1.y < p2.y || (abs(p1.y-p2.y) < eps && p1.x < p2.x);
}
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif // ONLINE_JUDGE
int n;
while (~scanf ("%d", &n))
{
memset(ans, false, sizeof(ans));
memset(pos, , sizeof(pos));
double minv1 = inf, minv2 = inf;
for (int i = ; i < n; i++)
{
double s, r;
scanf ("%lf%lf", &s, &r);
minv1 = min(/r, minv1); //减小误差
minv2 = min(minv2, /s);
p[i] = Point(/s, /r);
p[i].idx = i;
}
int tot = ConvexHull(n);
for (int i = ; i < tot; i++)
{
ans[cvx[i].idx] = true;
if (abs(cvx[i].y-minv1) < eps)
break;
}
for (int i = ; i < n; i++)
{
if (ans[p[pos[i]].idx] == true)
ans[p[i].idx] = true;
}
for (int i = ; i < n; i++)
if (ans[i] == true)
printf("%d ", i+);
printf("\n"); } return ;
}