\(x\) 軸を右方向、 \(y\) 軸を上方向にとるものとします。(通常の \(xy\) 平面と同様です)
このとき、問題は以下のように言い換えられます。

• \(xy\) 平面上の \(N\) 点が与えられる。以下の \(Q\) 個の質問に対する答えを足し合わせよ。
  • \(xy\) 平面上の直線が与えられるので、その直線上またはその直線よりも上側に存在する点の数を求めよ。

各質問に対し、全ての点について \(Y \ge A \times X + B\) かどうかを判定するので、その質問の時点で点が \(- A \times X + Y\) に関してソートできていればよいです(これをソート S とします)。なので、これを実現することを考えます。

まず、質問の直線を \(A\) の昇順にソートすることを考えます。

\(A = -\infty\) である場合から始めることになりますが、この場合は単に \((X,Y)\) を辞書順にソートすればよいです。

ソート S 上でのある \(2\) 点 \((X_l,Y_l)\) と \((X_r,Y_r)\) の順序を考えましょう。

• \(X_l = X_r\) である場合は常に \(Y_l < Y_r\) が保たれるように並びます。 (この \(2\) 点の順序が入れ替わることはありません。)
  
• そうでない場合、これらを結ぶ直線の傾きを超えるタイミングでソート S 上での順序が反転します。

以上から、例えば以下の解法が成立します。

• ソート S が成立するように点列を保持することを考える。
• 点列の隣接する \(2\) 点に関して、それらが今後傾きを増やしていくにあたって入れ替わるなら、入れ替わる傾きを記録しておき priority_queue で管理する。
• 実際に質問を処理していく。質問の処理の前に priority_queue を参照し、入れ替わっているべき \(2\) 点があるならそれがなくなるまで隣接点の swap を行う。
• 各質問は二分探索で処理する。

以上より、この問題に時間計算量 \(O(Q (\log Q + \log N) + N^2 \log N)\) で正解できます。

値を代入すると \(6.6 \times 10^8\) となりますが、実行時間制限が 10s であるため定数倍の悪い実装をしなければこの解法で AC を取ることができます。

実装例(C++):

#include<bits/stdc++.h>

using namespace std;
using pl=pair<long long,long long>;
using ppl=pair<pl,long long>;

long long g;
long long md=((1ll<<31)-1);
long long gen(){
  g = (48271*g) % md;
  return g;
}

long long comp_pl(pl a,pl b){
  long long l=a.first*b.second;
  long long r=a.second*b.first;
  if(l<r){return -1;}
  if(l>r){return 1;}
  return 0;
}

int main(){
  long long n;
  cin >> n;
  vector<pl> p(n);
  for(long long i=0;i<n;i++){
    cin >> p[i].first >> p[i].second;
  }
  sort(p.begin(),p.end());

  priority_queue<ppl,vector<ppl>,decltype(
    [](ppl a,ppl b){
      long long cp=comp_pl(a.first,b.first);
      if(cp==0){return (a.second>b.second);}
      if(cp==-1){return false;}
      return true;
    }
  )> pq;

  for(long long i=1;i<n;i++){
    if(p[i-1].first<p[i].first){
      ppl x;
      x.first={p[i].second-p[i-1].second,p[i].first-p[i-1].first};
      x.second=i;
      pq.push(x);
    }
  }

  long long q,ra,rb;
  cin >> q >> g >> ra >> rb;

  vector<pl> ask;
  for(long long i=0;i<q;i++){
    long long g1=gen();
    long long g2=gen();
    long long g3=gen();

    long long a = -ra + (g1%(2*ra+1));
    long long b = -rb + ((g2*md+g3)%(2*rb+1));
    ask.push_back({a,b});
  }

  sort(ask.begin(),ask.end());

  long long res=0;
  for(long long ak=0;ak<q;ak++){
    long long a=ask[ak].first;
    long long b=ask[ak].second;
    while(!pq.empty()){
      ppl od=pq.top();
      long long i=od.second;
      if(
        od.first!=make_pair(p[i].second-p[i-1].second,p[i].first-p[i-1].first)
      ){pq.pop();continue;}

      pl cp=od.first;
      pl cd={a,1};
      if(comp_pl(cp,cd)!=-1){break;}

      pq.pop();
      swap(p[i-1],p[i]);
      i--;
      if(i>0 && p[i-1].first<p[i].first){
        ppl x;
        x.first={p[i].second-p[i-1].second,p[i].first-p[i-1].first};
        x.second=i;
        pq.push(x);
      }
      i+=2;
      if(i<n && p[i-1].first<p[i].first){
        ppl x;
        x.first={p[i].second-p[i-1].second,p[i].first-p[i-1].first};
        x.second=i;
        pq.push(x);
      }
    }

    long long l=0,r=n-1;
    while(l<=r){
      long long te=(l+r)/2;
      if(p[te].second >= a*p[te].first+b){r=te-1;}
      else{l=te+1;}
    }

    res+=(n-1-r);
  }

  cout << res << "\n";
  return 0;
}