CF #526 Div.1 E: The Fair Nut and Rectangles

https://codeforces.com/contest/1083/problem/E

If we may use 128bit integers, this problem will be easier than the original one. The most difficult task is the comparison of two rational numbers with large digits. There exists a sophisticated method described below for solving this task without any floating point error. The time complexity is O(log n) because this method is almost the same as the Euclidean algorithm.

Given two rational numbers a/b, c/d. For convention, assume that both are positive. We first compare the integral parts. If they are not equal, we then compare the fractional parts. The comparison of integral parts is trivial. How do we compare the fractional parts without floating point numbers? If integral parts are equal, we just want to know whether the following inequality holds.

\[ \frac{a \bmod b}{b} < \frac{c \bmod d}{d}. \]

This is equivalent to

\[ \frac{b}{a \bmod b} > \frac{d}{c \bmod d} \]

if both a mod b and c mod d are not zero. Thus, applying this reformulation repeatedly, we finally obtain the desired result.

https://codeforces.com/contest/1083/submission/46880340

#include <cassert>

// b and d must be positive
bool cmp(long long a, long long b, long long c, long long d) {
    long long q1 = a >= 0 ? a / b : (a - b + 1) / b;
    long long q2 = c >= 0 ? c / d : (c - d + 1) / d;
    if (q1 != q2) return q1 < q2;
    long long r1 = a - b * q1;
    long long r2 = c - d * q2;
    if (r2 == 0) return false;
    if (r1 == 0) return true;
    return cmp(d, r2, b, r1);
}

bool cmp2(long long a, long long b, long long c, long long d) {
    return a * d < c * b;
}

int main() {
    for (int i = -100; i <= 100; i++) {
        for (int j = 1; j <= 100; j++) {
            for (int k = -100; k <= 100; k++) {
                for (int l = 1; l <= 100; l++) {
                    assert(cmp(i, j, k, l) == cmp2(i, j, k, l));
                }
            }
        }
    }
}

An entire source code is:

#include <stdio.h>
#include <algorithm>

using namespace std;

struct P {
    long long x, y;
    P(long long x_ = 0, long long y_ = 0) : x(x_), y(y_) {}
};

/* a*d - b*c < 0 */
bool cmp(long long a, long long b, long long c, long long d) {
    if (b == 0) return a < 0 && d > 0 || a > 0 && d < 0;
    if (d == 0) return b > 0 && c > 0 || b < 0 && c < 0;
    if (b < 0) return cmp(c, d, -a, -b);
    if (d < 0) return cmp(-c, -d, a, b);
    long long q1 = a >= 0 ? a / b : (a - b + 1) / b;
    long long q2 = c >= 0 ? c / d : (c - d + 1) / d;
    if (q1 != q2) return q1 < q2;
    long long r1 = a - b * q1;
    long long r2 = c - d * q2;
    if (r2 == 0) return false;
    if (r1 == 0) return true;
    return cmp(d, r2, b, r1);
}

bool cmp(P a, P b) {
    return cmp(a.x, a.y, b.x, b.y);
}

P operator-(P a, P b) {
    return P(a.x - b.x, a.y - b.y);
}

P H[1000000];
int L, R;

long long f(int k, long long x) {
    return H[k].x * x + H[k].y;
}

void push(P p) {
    while (R - L >= 2 && !cmp(H[R - 1] - H[R - 2], p - H[R - 1])) R--;
    H[R++] = p;
}

long long query(long long x) {
    while (R - L >= 2 && f(L, x) <= f(L + 1, x)) L++;
    return f(L, x);
}

int N;
struct A {
    long long x, y, a;
} Q[1000000];

bool operator<(A a, A b) {
    return a.x < b.x;
}

long long dp[1000000];

int main() {
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%lld %lld %lld", &Q[i].x, &Q[i].y, &Q[i].a);
    }
    sort(Q, Q + N);
    long long ans = 0;
    for (int i = 0; i < N; i++) {
        dp[i] = Q[i].x * Q[i].y - Q[i].a + max(0LL, query(-Q[i].y));
        push(P(Q[i].x, dp[i]));
        ans = max(ans, dp[i]);
    }
    printf("%lld\n", ans);
}