Expert.
Put your skills to the test.

Problem summary

Choose nonnegative real lengths for two race disciplines. Athlete i takes S1/V1[i]+S2/V2[i] time. Print the0-based indices of athletes who can be the unique fastest for some choice of lengths.

Constraints

2≤N≤100000;1≤V1,V2≤10000.

Worked example

Original statement sample, with whitespace restored where PDF extraction joined numbers.

4
1 4
2 2
4 1
3 3

0 2 3

Solution analysis

1. Associate athlete i with (1/V1,1/V2). A race minimizes the dot product of this point with the nonnegative vector(S1,S2). Only the decreasing lower convex boundary can support a unique minimum.
2. For each first speed, retain only the largest second speed; smaller second speeds are dominated. Scan first speeds from largest to smallest, retaining strictly improving second speeds, then build the lower hull. Remove collinear middle points: they can only tie.
3. Duplicate speed pairs share every race time, so neither athlete can win uniquely even if their shared point is a hull vertex. In the sample, (2,2) is dominated by(3,3); the other three have a supporting race direction. Orientation is computed exactly by clearing reciprocal denominators; each resulting term is a product of four speeds, safe in64bits.

Why it works

A minimizer of a linear function lies on a supporting boundary. Strict lower-hull vertices have an interval of supporting directions and therefore can be uniquely optimal; collinear interior points cannot. Dominated points cannot improve a nonnegative dot product. The retained endpoints are also achievable with one zero race length. Duplicate coordinates always tie.

Watch out. The required victory is unique. Do not accept duplicates or collinear interior points. Use the stated0-based athlete indices; use exact orientation rather than a floating-point epsilon.

An independently written complete program with standard headers.

#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
struct Point{
    long long a,b;
    int count,index;
};
long long turn(const Point&p,const Point&q,const Point&r){
    // Clear all six positive reciprocal denominators.
    return p.a*r.a*p.b*q.b+q.a*r.a*p.b*r.b+p.a*q.a*q.b*r.b-q.a*r.a*p.b*q.b-
        p.a*r.a*q.b*r.b-p.a*q.a*p.b*r.b;
}
int main(){
    int n;
    cin>>n;
    vector<int>best(10001,0),count(10001,0),index(10001,-1);
    for(int i=0;i<n;i++){
        int a,b;
        cin>>a>>b;
        if(b>best[a]){
            best[a]=b;
            count[a]=1;
            index[a]=i;
        }
        else if(b==best[a]){
            count[a]++;
        }
    }
    vector<Point>hull;
    int largestB=0;
    for(int a=10000;a>=1;a--){
        if(best[a]<=largestB){
            continue;
        }
        largestB=best[a];
        Point p{a,best[a],count[a],index[a]};
        while(hull.size()>=2&&turn(hull[hull.size()-2],hull.back(),p)<=0){
            hull.pop_back();
        }
        hull.push_back(p);
    }
    vector<int>answer;
    for(const Point&p:hull){
        if(p.count==1){
            answer.push_back(p.index);
        }
    }
    sort(answer.begin(),answer.end());
    if(answer.empty()){
        cout<<-1;
    }
    else{
        for(size_t i=0;i<answer.size();i++){
            if(i!=0){
                cout<<' ';
            }
            cout<<answer[i];
        }
    }
    cout<<'\n';
}