fork download 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <utility>
  6. #include <cmath>
  7. #include <queue>
  8. using namespace std;
  9.  
  10. #define in cin
  11. #define out cout
  12. #define X first
  13. #define Y second
  14.  
  15. class BIT
  16. {
  17. private:
  18.     int sz;
  19.     vector<int> vec;
  20.  
  21. public:
  22.     BIT(int n)
  23.     {
  24.         sz = 1; while(sz < n) sz *= 2;
  25.         vec.resize(sz*2+1, 0);
  26.     }
  27.  
  28.     void upd(int id)
  29.     {
  30.         id += sz-1;
  31.         while(id)
  32.         {
  33.             vec[id]++;
  34.             id /= 2;
  35.         }
  36.     }
  37.  
  38.     int get(int s, int e)
  39.     {
  40.         s += sz-1; e += sz-1;
  41.  
  42.         int ret = 0;
  43.         while(s<=e)
  44.         {
  45.             if(s % 2 == 1) ret += vec[s];
  46.             if(e % 2 == 0) ret += vec[e];
  47.             s++; s /= 2;
  48.             e--; e /= 2;
  49.         }
  50.  
  51.         return ret;
  52.     }
  53. };
  54.  
  55. int main()
  56. {
  57.     int tc; in >> tc;
  58.     while(tc--)
  59.     {
  60.         //input
  61.         int n; double p, q; in >> n >> p >> q;
  62.         vector< pair<double, double> > stars;
  63.         for(int i=1; i<=n; i++)
  64.         {
  65.             double x, y; in >> x >> y;
  66.             stars.push_back({x,y});
  67.         }
  68.  
  69.         //tan
  70.         vector< pair<double, int> > tan_p; //first for tan, second for id
  71.         for(int i=1; i<=n; i++) {
  72.             tan_p.push_back({atan2(stars[i-1].Y,stars[i-1].X-p), i});
  73.         } sort(tan_p.begin(), tan_p.end());
  74.  
  75.         int P[111111];
  76.         for(int i=1; i<=n; i++) P[i] = tan_p[i-1].Y;
  77.  
  78.         vector< pair<double, int> > tan_q;
  79.         for(int i=1; i<=n; i++) {
  80.             tan_q.push_back({atan2(stars[i-1].Y,stars[i-1].X-q), i});
  81.         } sort(tan_q.begin(), tan_q.end());
  82.  
  83.         int Qt[111111];
  84.         int Q[111111];
  85.         for(int i=1; i<=n; i++) Qt[i] = tan_q[i-1].Y;
  86.         for(int i=1; i<=n; i++) Q[Qt[i]] = i;
  87.  
  88.         BIT BIT_(n);
  89.         long long res = 0;
  90.         for(int i=1; i<=n; i++)
  91.         {
  92.             int t = Q[P[i]];
  93.             int sum = BIT_.get(t, n); res += sum;
  94.             BIT_.upd(t);
  95.         }
  96.  
  97.         out << res << endl;
  98.     }
  99.  
  100.  
  101.     return 0;
  102. }
Success #stdin #stdout 0s 4324KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/H3Wv51
language:
C++14 (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!