Pagini recente » Cod sursa (job #1041580) | Cod sursa (job #1939998) | Cod sursa (job #1365778) | Cod sursa (job #2805430) | Cod sursa (job #2117921)
#include <bits/stdc++.h>
using namespace std;
ifstream fi( "biathlon.in" );
ofstream fo( "biathlon.out");
const int maxn = 1e5 + 5;
const double eps = 1e-12;
struct point {
double x, y;
int idx;
bool operator < (const point &aux) const {
if (x == aux.x)
return y < aux.y;
return x < aux.x;
}
} v[maxn], stk[maxn];
int n, answer[maxn], ans;
bool stop[maxn];
double area(const point &a, const point &b, const point &c) {
return a.x*b.y - b.x*a.y + b.x*c.y - c.x*b.y + c.x*a.y - a.x*c.y;
}
bool compare( const point &a, const point &b ) {
double ar = area( v[ 1 ], a, b );
if (fabs( ar ) < eps)
return a.x < b.x;
return ar > eps;
}
int main()
{
int x, y;
fi >> n;
for (int i = 1; i <= n; i++) {
fi >> x >> y;
v[ i ].x = 10000.0 / x;
v[ i ].y = 10000.0 / y;
v[ i ].idx = i;
}
sort( v + 1, v + n + 1 );
for (int i = 1; i <= n; i++)
if (fabs( v[ i ].x - v[i - 1].x ) < eps && fabs( v[ i ].y - v[i - 1].y ) < eps)
stop[ v[ i ].idx ] = stop[ v[i - 1].idx ] = 1;
for (int i = 2; i <= n; i++)
if (v[ i ].x < v[ 1 ].x)
swap( v[ i ], v[ 1 ]);
sort( v + 2, v + n + 1, compare );
for (int i = 2; i <= n; i++) {
if (fabs( v[ i ].x - v[i - 1].x ) < eps && fabs( v[ i ].y - v[i - 1].y ) < eps)
stop[ v[ i ].idx ] = stop[ v[i - 1].idx ] = 1;
}
int top = 0;
stk[ ++top ] = v[ 1 ];
stk[ ++top ] = v[ 2 ];
for (int i = 3; i <= n; i++) {
while (top > 1 && area( stk[top - 1], stk[ top ], v[ i ] ) < -eps)
top--;
stk[ ++top ] = v[ i ];
}
int low = 1;
for (int i = 2; i <= top; i++)
if (stk[ i ].y < stk[ low ].y)
low = i;
for (int i = 1; i <= low; i++)
if (!stop[ stk[ i ].idx ])
answer[ ++ans ] = stk[ i ].idx - 1;
if (ans == 0)
fo << -1;
else {
sort( answer + 1, answer + ans + 1 );
for (int i = 1; i <= ans; i++)
fo << answer[ i ] << ' ';
}
fo.close();
fi.close();
return 0;
}