Fişierul intrare/ieşire:biathlon.in, biathlon.outSursăShumen 2016 - Seniori
AutorIvo DilovAdăugată deAndrei1998Andrei Constantinescu Andrei1998
Timp execuţie pe test1 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Biathlon

Piggy a decis sa organizeze o cursa de biatlon, in care participantii vor concura in doua discipline. Ea a invitat N competitori, care poseda urmatoarele caracteristici:

  • Fiecare competitor poseda vitezele V1 si V2 pentru cele doua discipline, respectiv.
  • Competitorii au viteze constante (V1 si V2) pe parcursul intregilor respectivelor trasee.
  • Distanta parcursa de competitor in timpul t1 in prima disciplina este S1 = V1 * t1 si distanta parcursa pentru cea de-a doua disciplina in timpul t2 este S2 = V2 * t2.
  • Competitorul invinge daca suma timpilor lui este unica cea mai mica dintre sumele timpilor tuturor competitorilor (altfel spus, este strict mai mica decat toate celelalte sume).

In calitate de organizator, Piggy poate alege orice distante doreste (numere reale nenegative S1 si S2) pentru fiecare dintre cele doua discipline. Acum ea se intreaba care dintre competitori sunt potentiali invingatori, pentru a determina daca exista S1 si S2 care sa le asigure victoria.

Determinati care dintre competitori pot invinge.

Date de intrare

Pe prima linie a fişierului de intrare biathlon.in se afla numarul N. Urmatoarele N linii contin cate doua numere intregi pozitive V1 si V2, separate prin spatiu: vitezele celui de-al i-lea competitor (pentru i = 0, 1, ..., N - 1).

Date de ieşire

Pe prima linie a fişierului de ieşire biathlon.out vor fi afisati indicii competitorilor care pot invinge. Indicii vor fi ordonati crescator, separati prin spatii. Indicii sunt numerotati de la 0. Aceasta linie trebuie sa contina numarul -1, in cazul in care nu exista un competitor care poate sa invinga.

Restricţii

  • Subtask 1 (20 puncte): 2 ≤ N ≤ 100, 1 ≤ V1, V2 ≤ 100
  • Subtask 2 (40 puncte): 2 ≤ N ≤ 5 000, 1 ≤ V1, V2 ≤ 10 000
  • Subtask 3 (40 puncte): 2 ≤ N ≤ 100 000, 1 ≤ V1, V2 ≤ 10 000

Exemplu

biathlon.inbiathlon.out
4
1 4
2 2
4 1
3 3
0 2 3
3
3 3
3 3
2 2
-1

Explicaţie

In primul exemplu pot castiga competitorii 0, 2 si 3. Cel cu indicele 0 castiga de exemplu pentru distantele S1 = 0 si S2 = 10; competitorul cu indicele 2 castiga pentru S1 = 10 si S2 = 0; cel cu indicele 3 invinge pe distantele S1 = 10 si S2 = 10. Competitorul cu indicele 1 nu poate castiga: el intotdeauna va fi invins de competitorul cu indicele 3.

In exemplul secund doar competitorii 0 si 1 pot obtine timp minimal, dar nici unul dintre timpi nu va fi unic.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?