Chcemy przygotować mieszankę przypraw, w której sól, pieprz i czosnek są w proporcji $S:P:G$. Mamy półkę z butelkami przypraw w różnych proporcjach i chcemy obsługiwać zmiany stanu półki (dodanie lub usunięcie butelki) oraz zapytania o minimalną liczbę butelek z półki, które potrzebne są, aby przygotować mieszankę $S:P:G$.
Zastanówmy się najpierw, jak wyglądałoby rozwiązanie zadania, gdybyśmy mieli tylko dwie przyprawy (czyli $G=0$ i w żadnej butelce nie ma czosnku). Jeśli sól i pieprz mają być w stosunku $S:P$, to znaczy, że w objętości 1 będziemy chcieli mieć $x = S/(S+P)$ soli oraz $1-x = P/(S+P)$ pieprzu. Zatem porządany stosunek możemy opisać jedną liczbą rzeczywistą $x$.
Każda butelka zawiera mieszankę soli i pieprzu w pewnym stosunku. Zatem dla $i$-tej butelki możemy ją opisać liczbą $x_i$.
Zastanówmy się, jakie proporcje możemy uzyskać, mieszając zawartości dwóch butelek $x_1$ i $x_2$ (załóżmy, że $x_1 \leq x_2$). Jeśli chcemy uzyskać objętość 1, to z pierwszej możemy wziąć $\alpha$ (dla $0 \leq \alpha \leq 1$), a z drugiej $1-\alpha$. Wtedy proporcja wyniesie $x_1 \alpha + x_2 (1-\alpha)$. Zmieniając $\alpha$, możemy uzyskać wszystkie liczby z przedziału od $x_1$ do $x_2$. Zatem uda nam się uzyskać $x$, jeśli $x_1 \leq x \leq x_2$.
Geometrycznie można to przedstawić tak, że uzyskamy wszystkie liczby na osi liczbowej pomiędzy $x_1$ i $x_2$.
Widać zatem, że nie będziemy potrzebowali więcej niż dwóch butelek. Bo jeśli mamy trzy butelki $x_1 \leq x_2 \leq x_3$, to dowolną propocję uzyskamy też, biorąc skrajne wartości $x_1$ oraz $x_3$. W ogólności wystarczy nam minimalna i maksymalna wartość $x_i$.
Ostatecznie kryterium jest następujące: jeśli $x = x_i$, to wystarczy nam użyć jednej butelki $i$. Jeśli $\min(x_i) \leq x \leq \max(x_i)$, to wystarczą nam dwie butelki. W przeciwnym wypadku się nie da.
Tak więc cały algorytm jest następujący: trzymamy wartości $x_i$ w strukturze danych multiset. Dzięki temu w czasie logarytmicznym możemy wykonać wszystkie potrzebne operacje: dodanie wartości, usunięcie wartości, sprawdzenie czy wartość istnieje, znalezienie najmniejszej i największej wartości.
Zatem całe rozwiązanie będzie działać w złożoności czasowej $O(n \log n)$.
W przypadku trzech przypraw, możemy stosunek $S:P:G$ wyrazić za pomocą pary liczb $(x,y)$, bo w objętości 1 weźmiemy $x = S/(S+P+G)$ soli, $y = P/(S+P+G)$ pieprzu i $1-x-y = G/(S+P+G)$ czosnku. Zatem $i$-tą butelkę możemy reprezentować za pomocą $(x_i,y_i)$. Wygodnie jest myśleć o tym geometrycznie, jako o punkcie $B_i = (x_i,y_i)$ na płaszczyźnie.
Dla dwóch butelek $B_1 = (x_1,y_1)$ i $B_2 = (x_2,y_2)$ uzyskamy tutaj wszystkie punkty postaci $B_1 \alpha + B_2 (1-\alpha)$ dla $0 \leq \alpha \leq 1$, czyli punkty na odcinku łączącym $B_1$ i $B_2$.
Tak więc, jeśli punkt $B = (x,y)$ jest równy któremuś $B_i$, to wystarczy jedna butelka, a jeśli leży na odcinku pomiędzy jakimiś $B_1$ i $B_2$, to wystarczą dwie butelki.
Jeśli mamy trzy punkty $B_1$, $B_2$ i $B_3$, które tworzą trójkąt, to możemy uzyskać z nich dowolny punkt, który leży wewnątrz lub na brzegu tego trójkąta. Punkty na brzegu leżą bowiem na odcinkach pomiędzy wierzchołkami trójkąta, a każdy punkt w trójkącie leży na odcinku pomiędzy pewnymi punktami na brzegu.
Okazuje się, że podobnie jak dla dwóch przypraw wystarczały dwie butelki, to w przypadku trzech przypraw zawsze wystarczą trzy butelki (o ile rozwiązanie istnieje). Wynika to z tego, że dla większej liczby punktów $B_1, \ldots, B_k$ możemy uzyskać dowolny punkt, który leży w otoczce wypukłej $B_1, \ldots, B_k$. A z kolei dowolny punkt w otoczce wypukłej leży na pewnym trójkącie z triangulacji tej otoczki wypukłej, zatem wystarczy wziąć trzy punkty będące wierzchołkami tego trójkąta.
Rozwiązanie zaimplementujemy z użyciem liczb całkowitych, zatem punkty $B_i = (x_i,y_i)$ będziemy trzymać w postaci ułamków zwykłych w strukturze point. Przez $B_0$ oznaczymy punkt odpowiadający stosunkowi $S:P:G$.
Aby stwierdzić, czy odpowiedź jest równa $1$, będziemy utrzymywali liczbę punktów $B_i$, które są równe $B$.
Aby stwierdzić, czy odpowiedź jest równa $2$, będziemy utrzymywać liczbę odcinków $B_i B_j$, które zawierają w swoim wnętrzu punkt $B$. Będziemy w tym celu utrzymywać multizbiór wektorów $V_i = B_i - B$ (przy czym nie potrzebujemy ich dokładnej długości, więc będziemy trzymać tylko unikalnego reprezentanta wyznaczającego kierunek/zwrot w strukturze angle). Dodając wektor $V_i$, patrzymy ile mamy w multizbiorze wektorów $-V_i$ i o tyle zwiększamy licznik odcinków.
W końcu, aby stwierdzić, czy odpowiedź jest równa $3$, musimy sprawdzić, czy punkt $B$ leży w otoczce wypukłej wszystkich punktów. Posortujmy wektory $V_i$ wokół punktu $B$ i niech $\alpha_i$ oznacza kąt pomiędzy wektorem $V_i$ a kolejnym wektorem $V_{i+1}$ w tym posortowanieu.
Można pokazać, że jeśli $B$ nie leży w otoczce, to jest pewna prosta $p$ przechodząca przez $B$, która nie przecina otoczki, zatem wszystkie wektory $V_i$ leżą po jednej stronie prostej $p$. Z tego wynika, że istnieją dwa kolejne wektory $V_i$ i $V_{i+1}$, pomiędzy którymi kąt $\alpha_i$ jest większy niż $180^\circ$.
Będziemy zatem utrzymywać liczbę kątów $\alpha_i$ większych niż $180^\circ$. Tak więc na multisecie wektorów będziemy utrzymywać posortowanie wokół punktu $B$, oraz podczas wkładania nowego wektora $V_i$ pomiędzy wektory $V_j$ oraz $V_{j+1}$, uaktualnimy liczbę kątów, odejmując kąt między $V_j$ i $V_{j+1}$ oraz dodając kąty między $V_j$ i $V_i$, a także między $V_i$ i $V_{j+1}$ (przy czym musimy tu uważać na zdegenerowane przypadki, kiedy różnych wektorów na multisecie jest mniej niż $3$).
Złożoność czasowa algorytmu będzie wynosić$O(n \log n)$:
const int N = 110000; int sf,pf,gf,n,k; int cnt_one,cnt_two,cnt_three; struct point { ll x,y,mian; point() : x(), y(), mian(1) { } point(ll _x, ll _y, ll _mian) { x = _x; y = _y; mian = _mian; ll d = __gcd(__gcd(x, y), mian); if (d < 0) { d *= -1; } x /= d; y /= d; mian /= d; if (mian < 0) { x *= -1; y *= -1; mian *= -1; } } }; bool operator==(const point& p, const point& q) { return p.x == q.x && p.y == q.y && p.mian == q.mian; } struct angle { ll x,y; angle(ll _x, ll _y) { x = _x; y = _y; ll d = __gcd(x, y); if (d < 0) { d *= -1; } x /= d; y /= d; } bool up() const { return y > 0 || y == 0 && x > 0; } }; __int128_t det(const angle& p, const angle& q) { return __int128_t(p.x) * q.y - __int128_t(p.y) * q.x; } bool operator<(const angle& p, const angle& q) { if (p.up() != q.up()) { return p.up(); } else { return det(p, q) > 0; } } bool operator==(const angle& p, const angle& q) { return !(p < q) && !(q < p); } bool bigger(const angle& p, const angle& q) { return det(p, q) < 0; } angle operator-(const angle& p) { return angle(-p.x, -p.y); } angle operator-(const point& p, const point& q) { ll x = p.x * q.mian - q.x * p.mian; ll y = p.y * q.mian - q.y * p.mian; return angle(x, y); } point pt[N],zero; multiset<angle> zbior_katy; int calc(multiset<angle>::iterator& it) { auto prev_it = prev(it == zbior_katy.begin() ? zbior_katy.end() : it); auto next_it = next(it) == zbior_katy.end() ? zbior_katy.begin() : next(it); return bigger(*prev_it, *it) + bigger(*it, *next_it) - bigger(*prev_it, *next_it); } bool three() { if (zbior_katy.empty()) return 0; if (zbior_katy.count(*zbior_katy.begin()) == zbior_katy.size()) return 0; return cnt_three == 0; } int main() { scanf("%d%d%d%d",&sf,&pf,&gf,&n); zero = point(sf, pf, sf+pf+gf); REP(i,n) { char typ; scanf(" %c",&typ); if (typ == 'A') { int s,p,f; scanf("%d%d%d",&s,&p,&f); pt[k] = point(s, p, s+p+f); if (pt[k] == zero) { cnt_one++; } else { angle kat = pt[k] - zero; auto it = zbior_katy.insert(kat); cnt_three += calc(it); cnt_two += zbior_katy.count(-kat); } k++; } else { int x; scanf("%d",&x); --x; if (pt[x] == zero) { cnt_one--; } else { angle kat = pt[x] - zero; auto it = zbior_katy.find(kat); cnt_three -= calc(it); zbior_katy.erase(it); cnt_two -= zbior_katy.count(-kat); } } int ans = 0; if (cnt_one > 0) { ans = 1; } else if (cnt_two > 0) { ans = 2; } else if (three()) { ans = 3; } printf("%d\n", ans); } }