Dang_Quan_10_Tin

TRIACU

Sep 22nd, 2021 (edited)
196
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define task "TRIACU"
  2. #include <iostream>
  3. #include <cstdio>
  4. #include <algorithm>
  5. using namespace std;
  6. using ll = long long;
  7.  
  8. constexpr int N = 2e3 + 5;
  9. int n;
  10.  
  11. struct Segment
  12. {
  13.     int l, c;
  14.    
  15.  bool operator<(const Segment &a) const
  16.     {
  17.         return l < a.l;
  18.     }
  19. } a[N];
  20.  
  21. void Read()
  22. {
  23.     cin >> n;
  24.     for (int i = 1; i <= n; ++i)
  25.         cin >> a[i].l >> a[i].c;
  26.  
  27.     sort(a + 1, a + n + 1);
  28. }
  29.  
  30. bool Get(const ll &x, const ll &y, const ll &z)
  31. {
  32.     return x * x + y * y > z * z && (x - y) * (x - y) < z * z;
  33. }
  34.  
  35. bool Check(ll x, ll y, ll z)
  36. {
  37.     // Bất đẳng thức tam giác
  38.     if (x + y <= z || y + z <= x || x + z <= y)
  39.         return false;
  40.     // Kiểm tra xem có phải tam giác nhọn không
  41.     return Get(x, y, z) && Get(y, z, x) && Get(x, z, y);
  42. }
  43.  
  44. void Sub_1()
  45. {
  46.     ll ans(0);
  47.     // Duyệt mọi cặp độ dài
  48.     for (int i = 1; i <= n; ++i)
  49.         for (int j = i + 1; j <= n; ++j)
  50.             for (int t = j + 1; t <= n; ++t)
  51.                 if (Check(a[i].l, a[j].l, a[t].l))
  52.                     ans += 1ll * a[i].c * a[j].c * a[t].c;
  53.  
  54.     cout << ans;
  55. }
  56.  
  57. void Sub_2()
  58. {
  59.     ll ans(0);
  60.     for (int i = 1; i < n; ++i) // Cố định i
  61.     {
  62.         ll cnt(a[i + 1].c);
  63.      // Hai con trỏ
  64.         for (int j = i + 1, t = i + 2; j < n; ++j)
  65.         {
  66.             cnt -= a[j].c;
  67.             while (t <= n && Check(a[i].l, a[j].l, a[t].l))
  68.                 cnt += a[t++].c;
  69.  
  70.             ans += 1ll * a[i].c * a[j].c * cnt;
  71.         }
  72.     }
  73.  
  74.     cout << ans;
  75. }
  76.  
  77.  
  78. int32_t main()
  79. {
  80.     ios::sync_with_stdio(0);
  81.     cin.tie(0);
  82.     cout.tie(0);
  83.     freopen(task ".INP", "r", stdin);
  84.     freopen(task ".OUT", "w", stdout);
  85.  
  86.     Read();
  87.     if (n <= 200)
  88.         Sub_1();
  89.     else
  90.         Sub_2();
  91. }
  92.  
RAW Paste Data