Cod sursa(job #2117921)

Utilizator antanaAntonia Boca antana Data 29 ianuarie 2018 19:39:09
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.18 kb
#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;
}