HackerRank Geometry – Best Sum

Challenge: Best Sum

Scor cont: 100.0 / 100

Submission status: Accepted

Submission score: 1.0

Submission ID: 464808483

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/best-sum/problem

Cerinta

You are given two arrays *A* and *B* of length **N**. Let S be the set of integers from 1 to **N**. Can you find the maximum possible value of (A<sub>i1</sub>+A<sub>i2</sub>+...+A<sub>ik</sub>)<sup>2</sup>+(B<sub>i1</sub>+B<sub>i2</sub>+...+B<sub>ik</sub>)<sup>2</sup> where {i1,i2...ik} is a non-empty subset of S?

**Input Format**  
The first line contains a single integer **T**, denoting the number of test cases.  
T testcases follow, each test case given in following format.  

    N  
    A1 A2 ... AN  
    B1 B2 ... BN  

**Output Format**  
For each test case, output the maximum possible value in one line.  

**Constraints**  
1 <= T <= 10  
1 <= N <= 1000  
-10<sup>6</sup> <= A<sub>i</sub>, B<sub>i</sub> <= 10<sup>6</sup>  

**Sample Input**  

    1  
    2  
    -1 5  
    4 -5  

**Sample Output**  

    50

**Explanation**  
All possible non-empty subsets for N = 2 of S = {1,2} are {1}, {2} and {1,2}. The maximum possible values of the above equation now are 

+ (-1)<sup>2</sup> + (4)<sup>2</sup> = 17  
+ (5)<sup>2</sup> + (-5)<sup>2</sup> = 50  
+ (-1 + 5)<sup>2</sup> + (4 - 5)<sup>2</sup> = 17

hence 50. 

**Timelimits**

Timelimits for this challenge can be seen [here](https://www.hackerrank.com/environment)

Cod sursa

#include <bits/stdc++.h>
using namespace std;

struct Event {
    long long dx, dy;
    int type;
    long long vx, vy;
};

static inline __int128 cross128(long long ax, long long ay, long long bx, long long by) {
    return (__int128)ax * by - (__int128)ay * bx;
}
static inline __int128 cross128(const Event& a, const Event& b) {
    return cross128(a.dx, a.dy, b.dx, b.dy);
}
static inline bool upper(const Event& e) {
    return (e.dy > 0) || (e.dy == 0 && e.dx > 0);
}
static inline bool polarLess(const Event& a, const Event& b) {
    bool ua = upper(a), ub = upper(b);
    if (ua != ub) return ua > ub;
    __int128 cr = cross128(a, b);
    if (cr != 0) return cr > 0;
    if (a.type != b.type) return a.type < b.type;
    if (a.vx != b.vx) return a.vx < b.vx;
    return a.vy < b.vy;
}
static inline bool sameDir(const Event& a, const Event& b) {
    if (cross128(a, b) != 0) return false;
    __int128 dot = (__int128)a.dx * b.dx + (__int128)a.dy * b.dy;
    return dot > 0;
}
static inline long long norm2(long long x, long long y) {
    __int128 v = (__int128)x * x + (__int128)y * y;
    return (long long)v;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int N;
        cin >> N;
        vector<long long> A(N), B(N);
        for (int i = 0; i < N; i++) cin >> A[i];
        for (int i = 0; i < N; i++) cin >> B[i];

        vector<Event> ev;
        ev.reserve(2 * N);

        long long sx = 0, sy = 0;

        for (int i = 0; i < N; i++) {
            long long vx = A[i], vy = B[i];
            if (vx == 0 && vy == 0) continue;

            if (vx > 0 || (vx == 0 && vy < 0)) {
                sx += vx;
                sy += vy;
            }

            ev.push_back(Event{ vy, -vx, +1, vx, vy});
            ev.push_back(Event{-vy,  vx, -1, vx, vy});
        }

        sort(ev.begin(), ev.end(), polarLess);

        long long best = norm2(sx, sy);

        for (size_t i = 0; i < ev.size(); ) {
            size_t j = i + 1;
            while (j < ev.size() && sameDir(ev[i], ev[j])) ++j;

            for (size_t t = i; t < j; t++) {
                if (ev[t].type == -1) { sx -= ev[t].vx; sy -= ev[t].vy; }
            }
            for (size_t t = i; t < j; t++) {
                if (ev[t].type == +1) { sx += ev[t].vx; sy += ev[t].vy; }
            }

            best = max(best, norm2(sx, sy));
            i = j;
        }

        cout << best << "\n";
    }

    return 0;
}