Advertisement
Dang_Quan_10_Tin

Sum of Vectors

Jun 29th, 2022
671
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. using Vector = pair<int, int>;
  6. #define x first
  7. #define y second
  8.  
  9. int cross(Vector x, Vector y) {
  10.     return x.x * y.y - x.y * y.x;
  11. }
  12.  
  13. int getQuater(Vector vec) {
  14.     auto [x, y] = vec;
  15.     if (x >= 0 && y >= 0) return 0;
  16.     if (x < 0 && y >= 0) return 1;
  17.     if (x < 0 && y < 0) return 2;
  18.     if (x >= 0 && y < 0) return 3;
  19.     return -1;
  20. }
  21.  
  22. bool comp(Vector vec1, Vector vec2) {
  23.     int quater1 = getQuater(vec1);
  24.     int quater2 = getQuater(vec2);
  25.     if (quater1 != quater2) return quater1 < quater2;
  26.     return cross(vec1, vec2) > 0;
  27. }
  28.  
  29. int main() {
  30.     ios::sync_with_stdio(false);
  31.     cin.tie(nullptr);
  32.    
  33.     int n;
  34.     cin >> n;
  35.     vector<Vector> vecs(n);
  36.     for (auto &vec : vecs) cin >> vec.x >> vec.y;
  37.     sort(vecs.begin(), vecs.end(), comp);
  38.  
  39.     long long best = 0;
  40.     int sumX = 0, sumY = 0;
  41.  
  42.     int p = n - 1, cnt = 0;
  43.  
  44.     auto update = [&]() {
  45.         best = max(best, 1LL * sumX * sumX + 1LL * sumY * sumY);
  46.     };
  47.  
  48.     for (int i = 0; i < n; i++) {
  49.         while (cnt < n && cross(vecs[i], vecs[(p + 1) % n]) >= 0) {
  50.             p = (p + 1) % n;
  51.             sumX += vecs[p].x, sumY += vecs[p].y;
  52.             cnt++;
  53.             update();
  54.         }
  55.         cnt--;
  56.         sumX -= vecs[i].x, sumY -= vecs[i].y;
  57.         update();
  58.     }
  59.  
  60.     cout << best << '\n';
  61.  
  62.     return 0;
  63. }
Advertisement
RAW Paste Data Copied
Advertisement