讲解 CF924D Contact ATC。

考虑转化为函数求零点问题，注意到单调性后转移为区间包含问题，树状数组维护即可。

思路：

考虑函数 \(\operatorname{F}(v_0)_i\) 表示风速为 \(v_0\) 时，\(i\) 到达原点的时间，易得：

\[\operatorname{F}(v_0)_i = \frac{x_i}{v_i+v_0}

\]

则若 \((i,j)\) 满足条件，需要满足 \(\operatorname{F}(v_0)_i\) 与 \(\operatorname{F}(v_0)_j\) 的交点的横坐标在 \([-m,m]\) 间，那么若 \(\operatorname{F}(v_0)_i=\operatorname{F}(v_0)_j\)，即 \(\operatorname{F}(v_0)_i-\operatorname{F}(v_0)_j=0\)。

根据零点存在定理：若区间 \([l,r]\) 满足 \(\operatorname{f}(l) \le 0\) 且 \(\operatorname{f}(r) \ge 0\)，且函数连续，则 \([l,r]\) 至少有一个 \(\operatorname{f}(x)\) 的零点。

那么判定 \(\operatorname{F}(v_0)_i-\operatorname{F}(v_0)_j=0\) 在 \([-w,w]\) 是否有零点，只需要满足 \(\operatorname{F}(-w)_i-\operatorname{F}(-w)_j \le 0\) 且 \(\operatorname{F}(w)_i-\operatorname{F}(w)_j \ge 0\)

注意到 \(\operatorname{F}(x)_i\) 有单调性，则设 \(l_i=\operatorname{F}(-w)_i,r_i=\operatorname{F}(w)_i\)。

则需要满足 \(l_i \le l_j<0\) 即 \(l_i \le l_j\)，且 \(r_i-r_j \ge 0\) 即 \(r_i \ge r_j\)。

那么若 \([l_i,r_i]\) 将 \([l_j,r_j]\) 包含，则 \((i,j)\) 是有贡献的，这个问题是简单题，不作多说，直接树状数组维护即可。

时间复杂度为 \(O(N \log N)\)。

注意离散化。

完整代码：

<code>#include<bits/stdc++.h>

#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)

#define lowbit(x) x&(-x)

#define pi pair<ll,ll>

#define pii pair<ll,pair<ll,ll>>

#define iip pair<pair<ll,ll>,ll>

#define ppii pair<pair<ll,ll>,pair<ll,ll>>

#define fi first

#define se second

#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x

#define Full(a) memset(a,0,sizeof(a))

#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);

#define For(i,l,r) for(int i=l;i<=r;i++)

#define _For(i,l,r) for(int i=r;i>=l;i--)

using namespace std;

typedef long double ld;

typedef double db;

typedef unsigned long long ull;

typedef long long ll;

bool Begin;

const ll N=1e6+10;

inline ll read(){

ll x=0,f=1;

char c=getchar();

while(c<'0'||c>'9'){

if(c=='-')

f=-1;

c=getchar();

}

while(c>='0'&&c<='9'){

x=(x<<1)+(x<<3)+(c^48);

c=getchar();

}

return x*f;

}

inline void write(ll x){

if(x<0){

putchar('-');

x=-x;

}

if(x>9)

write(x/10);

putchar(x%10+'0');

}

struct Node{

ll l,r;

bool operator<(const Node&rhs)const{

if(r!=rhs.r)

return r<rhs.r;

return l>rhs.l;

}

}A[N];

ll T,n,m,l1,l2,ans;

ld L[N],R[N],h1[N],h2[N];

ll x[N],v[N],a[N];

void add(ll x){

for(int i=x;i<=l1;i+=lowbit(i))

a[i]++;

}

ll query(ll x){

ll ans=0;

for(int i=x;i;i-=lowbit(i))

ans+=a[i];

return ans;

}

void work(ld &x){

x=floor(x*1e11)/1e11;

}

void solve(){

l1=l2=ans=0;

n=read(),m=read();

For(i,1,n){

x[i]=-read();

v[i]=read();

L[i]=(ld)x[i]/((ld)v[i]-m);

R[i]=(ld)x[i]/((ld)v[i]+m);

work(L[i]),work(R[i]);

h1[++l1]=L[i];

a[l1]=0;

h2[++l2]=R[i];

}

sort(h1+1,h1+l1+1);

l1=unique(h1+1,h1+l1+1)-(h1+1);

sort(h2+1,h2+l2+1);

l2=unique(h2+1,h2+l2+1)-(h2+1);

For(i,1,n){

A[i].l=lower_bound(h1+1,h1+l1+1,L[i])-h1;

A[i].r=lower_bound(h2+1,h2+l2+1,R[i])-h2;

//cerr<<A[i].l<<' '<<A[i].r<<'\n';

}

sort(A+1,A+n+1);

for(int i=1;i<=n;i++){

ans+=i-1-query(A[i].l-1);

add(A[i].l);

}

write(ans);

putchar('\n');

}

bool End;

int main(){

//open("wind.in","wind.out");

T=1;

while(T--)

solve();

return 0;

}