Vasilije mrzi geometriju

Interfejs

Pošaljite jedan C++23 izvorni fajl koji implementira sledeći interfejs:

int Pitaj(int i, int j, int k);
std::vector<std::pair<int, int>> ZapisiTacke(int N);
std::vector<int> Resi(int N, int Q);

Tekst zadatka

Василије, као и сваки нормалан програмер, мрзи геометрију, и нашао се у незгодној ситуацији. Наиме, док је Василије био у изласку са својом девојком Милицом, она му је рекла да воли геометрију. Василије се на ову реченицу јако збунио, па је Милица одлучила да му објасни лепоту геометрије. Како би успела у овоме, она је затражила од Василија да јој напише на папир различитих тачака у равни: N 9 9 Ti = (xi , yi ), 1 ≤ i ≤ N , −10 ≤ xi , yi ≤ 10

Она ће за то време замислити неку пермутацију: бројева од до , и игра креће. p = (p1 , p2 , … , pN ) 1 N

Василије може да пита Милицу следеће питање: За изабрана три различита индекса , какав је обилазак тачака: i, j, k ? Tp , Tp , Tp

Одговор може бити један од следећа три: i j k

, ако је обилазак позитиван, , ако је обилазак негативан, 1

, ако су тачке колинеарне. −1 0

За три тачке , и кажемо да су колинеарне ако постоји права која пролази кроз све три тачке. A B C

Ако тачке , и нису колинеарне, кажемо да је обилазак A B C позитиван ако се тачка налази са леве стране усмерене A → B → C C

праве од ка , а негативан ако се налази са десне стране те усмерене праве. A B

Василије жели да освоји Миличино срце, и мисли да ће то урадити успешно ако погоди њену пермутацију са што мање питања. Помозите Василију да нађе стратегију којом ће ово успешно урадити. Опис функција Потребно је да имплементирате функције: ZapisiT acke(N )

где је број тачака. Функција треба да запише тачке на којима ће се играти игра. N

Resi(N , Q)

где је број тачака, а дозвољени број питања. Функција треба да одреди Миличину пермутацију . N Q p

Ваш програм може да користи функцију P itaj(i, j, k)

која враћа одговор на питање какав је обилазак тачака . Tp , Tp , Tp

Индекси , и морају бити међусобно различити бројеви између и . i j k

i j k 1 N

Функција враћа: , ако је обилазак позитиван, P itaj(i, j, k)

1 Tp → Tp → Tp

, ако је обилазак негативан, i j k

−1 Tp i → Tp j → Tp k

0 , ако су тачке , и Tp Tp Tp колинеарне. Тачке су индексиране од до . i j k

1 N

Пермутација је фиксирана пре покретања ваше функције и не мења се током извршавања програма. Пример p

Један пример може изгледати овако: Нека је . N = 5

Користећи функцију ZapisiTacke, можете записати следећих 5 тачака: , , , , T1 = (0, 0) T2 = (1, 0) T3 = (2, 0) T4 = (0, 1) T5 = (1, −1), Нека је Миличина пермутација: p = [5, 3, 4, 2, 1]

Тада, на пример: Pitaj(2, 4, 5)посматра обилазак , односно Tp → Tp. → Tp T3 → T2 → T1

Пошто су ове три тачке колинеарне, функција враћа . 2 4 5

0

Pitaj(1, 2, 4) посматра обилазак . T5 → T3 → T2

Тачка се налази са леве стране усмерене праве од ка , па функција враћа . T2 T5 T3 1

Pitaj(5, 2, 1) посматра обилазак . T1 → T3 → T5

Тачка се налази са десне стране усмерене праве од ка , па функција враћа . T5 T1 T3 −1

Овај пример служи само за илустрацију начина на који функција Pitaj ради. У стварним тест примерима, пермутација је скривена од p

такмичара.

Након што Василије користећи довољно функција питај, сазна пермутацију , функција Resi треба да врати: { p X, 5, 3, 4, 2, 1 }, где X

може бити било која вредност која стаје у опсег c++ типа int . Ограничења Важи: 4 ≤ N ≤ 1000

Тест примери су подељени у неколико подзадатака. У сваком подзадатку је дато ограничење , које представља дозвољен број Q

позива функције . P itaj

[5 поена]: =p или = [1, 2, 3, … , N ] p , . [N , N − 1, … , 1] N ≤ 200, Q = 20000

20 поена: , . p1 = 1 N ≤ 200, Q = 25000

N ≤ 50, Q = 150000

N ≤ 200, Q = 25000

Q = 24000

Детаљи имплементације Q = 9400

Потребно је да пошаљете тачно један фајл који имплементира поменуту функцију. Осим тражене функције, ваш фајл може да садржи и додатне глобалне променљиве, помоћне функције и додатне библиотеке. Ваше функције морају бити следећег облика: vector<pair<int, int>> ZapisiTacke(int N) vector Resi(int N, int Q) Функција ZapisiTacke треба да врати тачке као низ парова индексиран од 1, дужине , где је прва вредност пара координата, а N + 1 x

друга вредност координата. y

Функција Resi треба да врати пронађену пермутацију као низ индексиран од 1, дужине p . N + 1

Ваш програм мора укључивати header code.h, у ком је дефинисана функција Pitaj следећег потписа: int Pitaj(int i, int j, int k) Уз задатак, обезбеђен вам је template фајл code.cpp који можете користити и мењати по потреби. Такође вам је обезбеђен програм grader.cpp који служи да лакше тестирате кодове. Овај програм учитава са стандардног улаза следеће податке: У првом реду налазе се бројеви и . N Q

Затим овај програм позива вашу функцију ZapisiTacke како би добила тачке на којима ће се играти игра. У следећем реду налази се пермутација . p1 , p2 , … , pN

Затим овај програм позива вашу функцију Resi и штампа повратну вредност на екран. Уколико ваше решење користи функцију Pitaj више од пута, биће прекинуто са статусом RTE (runtime error). Q

SIO2026Dan2Materijali.zip 