Advertisement
welleyth

E. Chemistry

Feb 15th, 2021
706
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.58 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define int long long
  6. #define pb push_back
  7. #define mp make_pair
  8. #define __int128 long long
  9.  
  10. signed main()
  11. {
  12.     ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
  13.  
  14. //    freopen("input.txt","r",stdin);
  15. //    freopen("output.txt","w",stdout);
  16.  
  17.     int n;
  18.     cin >> n;
  19.  
  20.     int p0,q0;
  21.     cin >> p0 >> q0;
  22.  
  23.     int g = __gcd(p0,q0);
  24.  
  25.     p0 /= g;
  26.     q0 /= g;
  27.  
  28.     vector<int> zero;
  29.  
  30.     int m,p,q;
  31.  
  32.     int a,b;
  33.  
  34.     set<pair<int,int> > st;
  35.  
  36.     map<pair<int,int>,int> pos;
  37.  
  38.     for(int i = 1; i <= n; i++)
  39.     {
  40.         cin >> m >> p >> q;
  41.         g = abs(__gcd(p,q));
  42.         p /= g;
  43.         q /= g;
  44.         if(p == p0 && q == q0)
  45.         {
  46.             zero.pb(i);
  47.             continue;
  48.         }
  49.         a = m * (p0 * q - p * q0);
  50.         b = q0 * q;
  51.         g = __gcd(a,b);
  52.         a /= g;
  53.         b /= g;
  54.         if(b < 0)
  55.             a = -a, b = -b;
  56.         st.insert(mp(a,b));
  57.         pos[mp(a,b)] = i;
  58.     }
  59.  
  60.     if(zero.size() > 1)
  61.     {
  62.         cout << "YES\n";
  63.         cout << zero[0] << " " << zero[1] << "\n";
  64.         return 0;
  65.     }
  66.  
  67.     int k;
  68.  
  69.     pair<int,int> P;
  70.  
  71.     for(auto x : st)
  72.     {
  73.         P = x;
  74.         P.first = -P.first;
  75.         if(st.count(P))
  76.         {
  77.             cout << "YES\n";
  78.             cout << pos[x] << " " << pos[P] << "\n";
  79.             exit(0);
  80.         }
  81.     }
  82.  
  83.     cout << "NO";
  84.  
  85.     return 0;
  86. }
  87. /*
  88.  
  89. n * (n+1) / 2 = M
  90. (n ^ 2 + n) = 2 * M
  91.  
  92. n ^ 2 + n - 2 * M = 0
  93. D = 1 + 8*M
  94.  
  95. n = (-1 + sqrt(D)) / 2
  96.  
  97.  
  98.  
  99.  
  100.  
  101.  
  102.  
  103. */
  104.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement