RT,就是官方题解的思路。
#include<bits/stdc++.h>
using namespace std;
const int N=5005,Q=10000005;
const long long INFB=1e16+5,MOD=((1ll<<31)-1);
long long gcd(long long a,long long b){return (b?gcd(b,a%b):a);}
struct fraction{
int u,d;
fraction(int _u=0,int _d=1){
int tmp=gcd(_u,_d);
_u/=tmp,_d/=tmp;
u=_u,d=_d;
}
friend fraction operator+(fraction a,fraction b){
long long tmpu=1ll*a.u*b.d+1ll*b.u*a.d,tmpd=1ll*a.d*b.d;
return fraction(int(tmpu/gcd(tmpu,tmpd)),int(tmpd/gcd(tmpu,tmpd)));
}
friend fraction operator+(fraction x,int k){
long long tmpu=x.u+1ll*k*x.d;
return fraction(int(tmpu/gcd(tmpu,x.d)),int(x.d/gcd(tmpu,x.d)));
}
friend fraction operator*(fraction x,int k){
long long tmpu=1ll*x.u*k;
return fraction(int(tmpu/gcd(tmpu,x.d)),int(x.d/gcd(tmpu,x.d)));
}
fraction operator-(){return {-u,d};}
friend bool operator<(fraction x,fraction y){return 1ll*x.u*y.d<1ll*y.u*x.d;}
friend bool operator<=(fraction x,int y){return x.u<=1ll*y*x.d;}
friend bool operator>=(fraction x,int y){return x.u>=1ll*y*x.d;}
friend bool operator<=(fraction x,fraction y){return 1ll*x.u*y.d<=1ll*y.u*x.d;}
};
const fraction INFA={-100000005,1};
struct will_swap{
short int a,b;fraction t;
will_swap(short int _a=0,short int _b=0,fraction _t=fraction()){a=_a,b=_b,t=_t;}
}s[N*N];
struct line{
int k,b,num;
line(int _k=0,int _b=0,int _num=0){k=_k,b=_b,num=_num;}
fraction calc(fraction x){return x*k+b;}
}li[N];
struct query{
int a;long long b;
query(int _a=0,long long _b=0){a=_a,b=_b;}
}q[Q];
bool cmp_query(query x,query y){return x.a<y.a;}
bool cmp_swap(will_swap x,will_swap y){return x.t<y.t;}
bool cmp_line(line x,line y){return x.calc(INFA)<y.calc(INFA);}
fraction get_swap(line x,line y){
if(x.k==y.k) return {100000005,1};
return fraction((y.b-x.b),(x.k-y.k));
}
int n,m,rnk[N],to[N];
int swap_num,swap_cnt;
long long g_0,ra,rb,ans;
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n;
for(short int i=1,x,y;i<=n;i++){
cin>>x>>y;
li[i]=line(-x,y,i);
}
sort(li+1,li+n+1,cmp_line);
for(short int i=1;i<=n;i++) rnk[i]=li[i].num,to[li[i].num]=i;
for(short int i=1;i<=n;i++){
for(short int j=i+1;j<=n;j++){
fraction pos=get_swap(li[i],li[j]);
if(INFA<=pos) s[++swap_num]=will_swap(li[i].num,li[j].num,pos);
}
}
stable_sort(s+1,s+swap_num+1,cmp_swap);
cin>>m>>g_0>>ra>>rb;
const long long MODA=2*ra+1,MODB=2*rb+1;
for(int i=1;i<=m;i++){
int g_1=(48271ll*g_0)%MOD,g_2=(48271ll*g_1)%MOD,g_3=(48271ll*g_2)%MOD;
// cerr<<i<<" "<<-ra+g_1%MODA<<" "<<-rb+(g_2*MOD+g_3)%MODB<<"\n";
q[i]=query(-ra+g_1%MODA,-rb+(g_2*MOD+g_3)%MODB);
g_0=g_3;
}
sort(q+1,q+m+1,cmp_query);
swap_cnt=1;
// for(int i=1;i<=n;i++) cerr<<rnk[i]<<" ";
// cerr<<"\n";
// for(int i=1;i<=swap_num;i++) cerr<<s[i].a<<" "<<s[i].b<<" "<<s[i].t<<"\n";
// cerr<<"\n";
// for(int i=1;i<=n;i++) cerr<<fixed<<setprecision(5)<<li[i].calc(-INFA-0.1)<<"\n";
// cerr<<"\n";
for(int i=1;i<=m;i++){
while(s[swap_cnt].t<=q[i].a&&swap_cnt<=swap_num){
swap(rnk[to[s[swap_cnt].a]],rnk[to[s[swap_cnt].b]]);
swap(li[to[s[swap_cnt].a]],li[to[s[swap_cnt].b]]);
swap(to[s[swap_cnt].a],to[s[swap_cnt].b]);
swap_cnt++;
}
// cerr<<q[i].a<<" "<<"cnt:"<<swap_cnt<<" ";
// for(int j=1;j<=n;j++) cerr<<rnk[j]<<" ";
// cerr<<"\n";
// for(int j=1;j<=n;j++) cerr<<fixed<<setprecision(5)<<li[rnk[to[j]]].calc(q[i].a)<<" "<<li[rnk[to[j]]].num<<"\n";
// cerr<<"\n";
short int l=1,r=n;
while(l<r){
short int mid=(l+r+1)>>1;
if(li[rnk[to[mid]]].calc(q[i].a)>=q[i].b) r=mid-1;
else l=mid;
}
// cerr<<q[i].a<<" "<<q[i].b<<" "<<i<<" "<<l<<"\n";
ans+=n-l;
}
cout<<ans<<"\n";
}