Радоје
Аутор: Марко Миленковић
Текст: и тест примери: Марко Миленковић
Анализа решења: Марко Миленковић
Тестирање: Јован Бенгин
Напомена
За потребе лакшег изражавања, лишће репрезентације Србије називаћемо плавим тачкама, а остала лишћа црвеним тачкама.
1. Сво лишће туђих репрезентација се налази у троуглу који формирају листови репрезентације Србије.
У овом подзадатку, оптималан круг биће описани круг око три плаве тачке. Ипак, како су све црвене тачке унутар троугла, можемо да закључимо да ће све црвене тачке и бити у описаном кругу. Тако да је решење у овом позадатку једноставно n.
2. Постоји неки максимални скуп S лишћа који Радоје може да украде и који се налази у кругу који формирају листови репрезентације Србије.
У овом подзадатку, потребно је пронаћи описани круг плавих тачака и проверити које тачке се налазе у њему. Центар круга налазимо као пресек симетрала неке две странице троугла. Затим, полупречник као растојање од центра до произвољне плаве тачке. За више детаља: Program to find Circumcenter of a Triangle | GeeksforGeeks
3. n, T <= 10
У овом подзадатку можемо проверити за сваки подскуп црвених тачака, да ли најмањи круг који их садржи, садржи и неку плаву тачку. За решење бирамо највећи подскуп за који се то не дешава.
Нека је неки S максимални скуп лишћа који Радоје може да украде. Постоји права којој је са једне стране скуп S, а са друге стране лишће репрезентације Србије.
Уочимо сценарио из описа овог подзадатка. Поменуту праву можемо да померамо ка плавом троуглу, док не “ударимо” у теме троугла. На овај начин дефинитивно нисмо смањили број црвених тачака у полуравни коју ова права дефинише.
Круг је једнозначно дефинисан својим полупречником и тангентом на тачки на ободу. Можемо као тачку на ободу да фиксирамо као теме плавог троугла и поменуту праву од раније као тангенту. Затим ако центар круга померамо у супротном смеру од плавог троугла (формално нормално у односу на тангенту), круг ће расти и у једном тренутку покупиће све црвене тачке које се налазе са друге стране праве. По услову подзадатка, ово је највећи скуп који можемо да покупимо.
Како бисмо пронашли овај скуп у пракси, за сваку плаву тачку сортирамо црвене тачке у циркуларном редоследу. Помоћу клизајућег прозора тражимо скуп црвених тачака где прва и последња формирају угао са плавом тачком мањи од 180 степени. Ово можемо замислити као да ротирамо праву око плаве тачке и гледамо које црвене се налазе са супротне стране у односу на троугао. И све те тачке смо показали да можемо да покупимо кругом.
Сложеност овог приступа је \mathcal{O}(n\log n).
4. n <= 100, T <= 5
За сваку тројку црвених тачака можемо да пронађемо описани круг. Ако овај круг садржи плаву тачку, игноришемо га. У супротном, избројимо колико црвених тачака је у њему и решење ће бити круг са најбише црвених тачака унутра.
5. Без додатних ограничења
Посматрајмо оптималан круг. Постоји неколико могућих сценарија:
Оптималан круг садржи три плаве тачке на ободу
Ово је други подзадатак. Потребно је пронаћи описани круг плавог троугла.
Оптимални круг садржи две плаве тачке на ободу
Центар круга се онда налази на симетрали ове две тачке. Идеја нам је да померамо центар круга (када фиксирамо центар и две тачке на ободу, јасно је да је круг јединствен) од центра описаног круга па ка бесконачности (у супротном смеру од треће плаве тачке). Међу свим овим опцијама бирамо круг са највише црвених тачака. Међутим, проблем настаје што имамо сувише опција.
Претпоставимо да је симетрала наше две плаве тачке део x-осе. Ово смемо да претпоставимо јер увек можемо да потирамо и транслирамо раван тако да важи. Знамо тачну вредност x-координате која представља границу до описаног круга (ако прекорачимо ову вредност, ухватићемо трећу плаву тачку унутар круга, што није дозвољено). За сваку црвену тачку желимо да нађемо интервал на x-оси за који важи да када је центар круга у њему, црвена тачка ће бити у кругу. Уколико се црвена тачка налази лево (супротно од треће плаве тачке) од странице троугла коју формирају наше две плаве тачке, онда ће црвена тачка бити у кругу од минус бесконачности до неке вредности x_o. Уколико је црвена тачка с десне стране, онда ће тачка бити у кругу од неке вредности x_o до центра описаног круга.
Нека су координате црвене тачке (x,y). Нека су координате једне од две плаве тачке (x_p, y_p) Желимо да израчунамо вредност x_o. Нека је r полупречник тренутног круга. Онда важи:
\begin{eqnarray*}
(x-x_o)^2 + (y-y_o)^2 &\leq& r^2\\
(x-x_o)^2 + (y-0)^2 &\leq& (x_p - x_o)^2 + (y_p - 0)^2\\
x^2 - 2xx_o + x_o^2 + y^2 &\leq& x_p^2 -2x_px_o + x_o^2 + y_p^2\\
2x_px_o - 2xx_o &\leq& x_p^2 + y_p^2 - x^2 -y^2\\
x_o\cdot2(x_p-x) &\leq& x_p^2 + y_p^2 - x^2 -y^2\\
\end{eqnarray*}
Сада разликујемо три случаја, да ли је x_p - x позитивно, негативно или нула:
-
Ако је x_p - x = 0, то значи да је (x,y) колинеарно са две плаве тачке. По тексту задатка знамо да су све тачке у општем положају, тако да овај случај није могућ
-
Ако је x_p - x > 0, то значи да је (x,y) “лево” од двеју плавих тачака. Онда сваки круг чији је центар у (x_o, 0) где важи x_o \leq \frac{x_p^2 + y_p^2 - x^2 -y^2}{2(x_p-x)}, садржи црвену тачку (x,y). За остале центре, чија је x-координата већа од овог разломка, тачка (x,y) није у њима.
-
Ако је x_p - x < 0, то значи да је (x,y) “десно” од двеју плавих тачака. Онда сваки круг чији је центар у (x_o, 0) где важи x_o \geq \frac{x_p^2 + y_p^2 - x^2 -y^2}{2(x_p-x)}, садржи црвену тачку (x,y). За све остале центре, чија је x-координата мања од овог разломка, тачка (x,y) није у њима.
Сада можемо да применимо технику клизајућег прозора. Сортирамо тачке по вредности x_o (само оне тачке које не пробијају границу за центар описаног круга). У почетку све тачке које су лево од двеју плавих тачака бивају у почетном кругу (замишљамо да је центар круга у минус бесконачности). Онда померамо центар круга на следећу вредност x_o. Уколико је ово вредност за црвену тачку лево од плавих тачака, онда смањујемо бројач. Уколико је ово вредност за црвену тачку десно од плавих тачака, онда повећавамо бројач. Решење је највећи бројач у било ком тренутку.
Временска сложеност овог решења је \mathcal{O}(n\log n)
Оптимални круг садржи једну плаву тачку на ободу
Уколико померамо центар круга у супротном смеру од плаве тачке, круг ће расти и увек бити надскуп почетног круга. Уколико у било ком тренутку круг “удари” у другу плаву тачку, налазимо се у претходном случају, који смо већ покрили и не морамо ништа да решавамо.
Уколико круг може бесконачно да расте, падамо у четврти подзадатак, који смо већ видели како можемо да решимо.
Оптимални круг не садржи ниједну плаву тачку на ободу
Фиксирамо центар и повећавамо полупречник. У једном тренутку морамо да “ударимо” у плаву тачку и онда упадамо у претходни случај.
Дакле, укупна сложеност целог решења је \mathcal{O}(n\log n)