Гриц
Аутор: Иван Стошић
Текст и тест примери: Иван Стошић
Анализа решења: Иван Стошић
Тестер: Никола Пешић
Анализа
На основу ограничења y_i \geq H можемо закључити да ће, уколико посматрамо произвољну вертикалну праву која пролази кроз кекс, у сваком тренутку, пресек преосталог кекса са том правом бити или празан, или ће бити једна дуж. Кад ово ограничење не би постојало, било би могуће да Павле поједе парче из “средине” кекса, у том случају би тај пресек могао да се састоји из више дужи. Основна идеја која је заједничка свим решењима јесте да се одржава низ b, где је b_i преостало парче кекса на позицији x = i. У почетку, пре свих упита имамо b_i = 0 за свако i \in [0, W]. Треба обратити пажњу при имплементацији да се не штампа негативан број, односно, ако неки круг прелази икс-осу, не треба смањивати b_i испод 0.
У првом подзадатку, радијус круга је 1, па су измене на низу b тривијалне - уколико круг има y=H, стављамо b_{x} = H-1.
У другом подзадатку, постављамо b_x = \min(b_x, y-2) и b_{x-1} = \min(b_{x-1}, y - \sqrt{3}), слично за b_{x+1}, наравно, уколико су ове x-координате у сегменту [0, W]. Временска сложеност решења прва два подзадатка је O(Q + W).
Трећи подзадатак је уопштење претходне идеје. Тачна вредност на коју треба поставити број b_i је \min(b_i, y - \sqrt{(R+i-x)(R-i+x)}) за све i \in [0, W] \cap [x-R, x+R]. Ова формула се може извести геометријски, помоћу Питагорине теореме. Временска сложеност је O(W + QR).
За решавање четвртог и петог подзадатка неопходне су нам следеће опсервације. Прва је та да је довољно посматрати облик који формирају доњи полукружни лукови додатих кругова. Друга, кључна је да се ниједна два таква лука не могу сећи више од једном, осим ако се не поклапају. Ово се може доказати на следећи начин: Посматрајмо нека два круга. Уколико се они не поклапају, они се могу сећи на највише два места. На основу тога што имају исти радијус, тачке пресека су централно симетрично распоређене у односу на тачку која се налази на средини дужи која спаја центре та два круга. Како овај центар има y-координату већу него “нижи” од та два круга, и једна од пресечних тачака сигурно исто има већу y-координату од центра нижег друга, па не учествује у пресеку доњих полукружница.
Четврти подзадатак се може решити тако што се експлицитно израчуна облик кекса. Сортирамо све кругове по x-координати и обрађујемо их у овом редоследу. Помоћу стека одржавамо скуп полукружница које учествују у коначном облику кекса, као и позиције пресека суседних полукружница. Одговор на неки упит можемо наћи бинарном претрагом по добијеном низу полукружница, или једноставније, обрадом целог низа полукружница тј. експлицитним налажењем свих вредности b_i, у једном пролазу кроз низ. Ово решење је применљиво управо зато што се сваке две полукружнице секу највише једном. Ову идеју није могуће применити уколико то не би важило, на пример, ако би се радијуси датих кружница разликовали. Временска сложеност је O(W + Q \log Q).
Одавде је јасно да решење четвртог подзадатка подсећа на оно што се зове “трик са конвексним омотачем”, где се налази облик који формира пресек полуравни. Други начин да се израчуна овај пресек полуравни јесте помоћу такозваног LiChao сегментног стабла, па је природно покушати прилагодити ту структуру података за овај проблем.
Наиме, формирајмо сегментно стабло, где се у сваком чвору налази опис једне полукружнице, која цела покрива придружени сегмент у стаблу, односно, таква да ако је чвор одговоран за сегмент [x_l, x_r], тада за кружницу важи x-R \leq x_l \leq x_r \leq x+R (услов 1), где је (x,y) њен центар. Додатно, намећемо ограничење да за лист, тј. чвор који одговара сегменту [x, x], пут у стаблу од тог листа до корена садржи круг који у x достиже најмању y-координату, у сваком тренутку. Ако ово важи, јасно је да на упит можемо одговорити у O(\log W), само посматрањем тих O(\log W) чворова на путу од листа до корена.
Како додати нови круг? Посматрајмо рекурзивну функцију која полази од корена стабла, који одговара чвору који чува сегмент [0, W]. Уколико за тренутни чвор не важи услов 1, и сегменти који одговарају кругу и чвору се не секу, можемо одмах изаћи, иначе рекурзивно додајемо круг у оба чвора детета тренутног чвора. На даље претпоставимо да услов 1 важи. Ако у тренутном чвору нема никаквог круга, слободно можемо ставити у тај чвор нови круг и изаћи из функције. Још један случај где можемо одмах ставити круг и изаћи јесте ако је нови полукруг цео испод старог на целом сегменту тренутног чвора [x_l, x_r], што се може једноставно проверити ако израчунамо y-координате пресека полукругова са [x_l, x_r], као по формули датој у решењу подзадатка 3. Уколико је нови полукруг цео изнад старог на том сегменту, не морамо да га додајемо, већ одмах излазимо из функције. Иначе, ова два полукруга се секу на тачно једном месту, унутар сегмента. У тај чвор можемо уписати онај од та два круга који је “доминантан” на бар једној половини сегмента, док други можемо рекурзивно убацити у друго дете тренутног чвора. Временска сложеност овог поступка се разликује од оног за обично сегментно стабло. У току рекурзије долазимо до O(\log W) чворова за које важи услов 1, а за сваки од њих имамо по један рекурзивни пут који се може састојати из највише O(\log W) чворова, па је временска сложеност додавања једног круга O(\log^2W), а целог решења O(W + Q \log^2 W).