Buenasss. Estuve resolviendo este problema: Codeforces - The Fair Nut and Rectangles.
Es de las primeras veces que implemento el Convex Hull Trick y me encontré con un gran problema al momento de encontrar intersecciones entre rectas: comparar fracciones.
Dejo mi código por si alguien quiere ver cómo va
#include <iostream>
#include <assert.h>
#include <algorithm>
#include <vector>
#include <deque>
#define DBG(x ) cerr<<#x<<" = "<<(x)<<endl
#define DBG2(x, y ) cerr<<#x<<" = "<<(x)<<", "<<#y<<" = "<<(y)<<endl
#define DBG3(x, y, z ) cerr<<#x<<" = "<<(x)<<", "<<#y<<" = "<<(y)<<", "<<#z<<" = "<<(z)<<endl
#define DBG4(x, y, z, w) cerr<<#x<<" = "<<(x)<<", "<<#y<<" = "<<(y)<<", "<<#z<<" = "<<(z)<<", "<<#w<<" = "<<(w)<<endl
#define RAYA cerr<<" =============== "<<endl
#define forn(i, n) for(int i = 0; i < int(n); i++)
#define fort(i, n) for(int i = 0; i <= int(n); i++)
#define fori(i, a, n) for(int i = a; i < int(n); i++)
#define forit(i, a, n) for(int i = a; i <= int(n); i++)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
template<typename T>
ostream & operator<<(ostream &os, const vector<T> &v){
os<<"[";
forn(i, (int) v.size()){
if(i) os<<", ";
os<<v[i];
}
os<<"]";
return os;
}
template<typename S, typename T>
ostream & operator<<(ostream &os, const pair<S, T> &p){
os<<"("<<p.first<<", "<<p.second<<")";
return os;
}
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef ll T;
typedef pair<T,T> Fraction;
struct Line{
T m, c;
T getY(T x){
return m * x + c;
}
Fraction interX(const Line& o){
return {o.c - c, m - o.m};
}
};
bool operator >= (Fraction a, Fraction b){
if(a.first == 0 || b.first == 0) return a.first >= b.first;
if(a.first / a.second > b.first / b.second) return 1;
if(b.first / b.second > a.first / a.second) return 0;
a.first %= a.second;
b.first %= b.second;
return a.first * b.second >= b.first * a.second;
}
bool bad(Line& a, Line& b, Line& c){
auto p = b.interX(a), q = c.interX(b);
return p >= q;
}
bool operator >= (pair<T,T> a, T b){
return a.first >= b * a.second;
}
struct Rect{
T x, y, a;
bool operator < (const Rect& o) const{
return x < o.x;
}
};
void solve(){
int n;
cin>>n;
vector<Rect> rects(n);
for(auto& rect : rects) cin>>rect.x>>rect.y>>rect.a;
sort(all(rects));
ll ans = 0;
deque<Line> ch{{0,0}};
for(auto rect : rects){
int sz = ch.size();
while(sz >= 2 && ch[sz-1].interX(ch[sz-2]) >= rect.y){
ch.pop_back(), sz--;
}
T c = ch.back().getY(rect.y) + rect.x * rect.y - rect.a;
ans = max(ans,ll(c));
Line aux = {-rect.x,c};
while(sz >= 2 && bad(aux, ch[0], ch[1])) ch.pop_front(), sz--;
ch.push_front(aux);
}
cout<<ans<<"\n";
}
int main(){
cin.tie(NULL);
ios::sync_with_stdio(0);
#ifdef LOCAL
freopen("input.in", "r", stdin);
#else
//~ freopen("input.in", "r", stdin);
//~ freopen("output.out", "w", stdout);
#endif
#ifdef LOCAL
int tcs;
cin>>tcs;
while(tcs--) solve();
#else
solve();
#endif
return 0;
}
Entendiendo lo siguiente:
Me surgió pensar en qué pasaría si a = 0 y d < 0 o c = 0 y b < 0. Podría generar una respuesta errónea, como el siguiente ejemplo.
Cuando los valores reales para las fracciones serían:
En el problema que estaba resolviendo no hubo mucho problema porque se podían hacer los cálculos en cierto orden tal que el denominador nunca quede en negativo.
struct Line{
T m, c;
T getY(T x){
return m * x + c;
}
Fraction interX(const Line& o){
return {o.c - c, m - o.m};
}
};
Al estar ordenadas las rectas por pendiente, el método interX se debe llamar desde la recta con mayor pendiente para evitar hacer un if.
Otro de los problemas fue el overflow del long long. En mi código, cada estado de la programación dinámica dp_i lo agrego como recta de la forma -\text{rectangulo}_x \times x + dp_i lo que hace que para insertarla tenga que usar el código:
Line aux = {-rect.x,c};
while(sz >= 2 && bad(aux, ch[0], ch[1])) ch.pop_front(), sz--;
ch.push_front(aux);
La función bad tiene lo siguiente:
bool bad(Line& a, Line& b, Line& c){
auto p = b.interX(a), q = c.interX(b);
return p >= q;
}
Y acá el gran problema: Si comparamos las fracciones p y q de la forma que mostré arriba, es decir \text{p}_\text{fst} \times \text{q}_\text{snd} \geq \text{q}_\text{fst} \times \text{p}_\text{snd} puede ocurrir que \text{p}_\text{fst} o \text{q}_\text{fst} lleguen a 10^{18} por lo que multiplicarlos por otro valor que puede llegar a 10^9 hace que supere el límite del long long. Para solucionar esto, hice el siguente código:
bool operator >= (Fraction a, Fraction b){
if(a.first == 0 || b.first == 0) return a.first >= b.first;
if(a.first / a.second > b.first / b.second) return 1;
if(b.first / b.second > a.first / a.second) return 0;
a.first %= a.second;
b.first %= b.second;
return a.first * b.second >= b.first * a.second;
}
Lo cual soluciona el problema, pero lo hace más lento al involucrar varias divisiones (la solución ocupa 1093 ms).
Siento que no debería ser tan difícil trabajar con fracciones o tal vez no debieron ser las protagonistas en mi solución cuando el problema trataba de Convex Hull Trick y por eso surge mi duda:
¿Hay una forma más fácil y eficiente de trabajar y comprar fracciones?
Igualmente teniendo en cuenta que el post original iba a tratar de tunear la constante, hacer una división entera (por un número arbitrario) es famosamente una operación super lenta en los procesadores habituales, así que esperaría que usar int128 sea mucho más rápido. ¡Pero habría que testearlo!