原题链接：E - Manhattan Multifocal Ellipse
题意：给n个点和一个最大距离d，求出有多少个点距离这n个点的距离总和小于等于d。
思路：前缀和，双指针。题目中要求的距离是曼哈顿距离，曼哈顿距离很特殊的一点是，对于二个点来说它们的x距离和y距离可以相互独立计算。观察数据范围，可以发现的是x和y的范围在[-1e6,1e6]之间，d的范围是[0,1e6]。那么就可以知道能够满足距离总和小于d的点的x和y坐标范围是在[-2e6,2e6]之间，可以分别计算出全部可能的x位置，这个位置上和n个点x的距离总和，y也同理，然后双指针的寻找全部的符合条件的x和y。
//冷静，冷静，冷静
//调不出来就重构
#pragma GCC optimize(2)
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
const int N=1e6+10,mod=1000000007;
vector<ll> solve(vector<ll> &a)
{sort(a.begin(),a.end());ll pre=0,rep=accumulate(a.begin(),a.end(),0ll);ll it=0;vector<ll> op;for(int i=-2e6;i<=2e6;i++){while(it<a.size()&&a[it]<i){pre+=a[it];rep-=a[it];it++;}ll sum=it*i-pre+rep-(a.size()-it)*i;op.push_back(sum);}sort(op.begin(),op.end());return op;
}
void Jiuyuan()
{ll n,d;cin>>n>>d;vector<ll>p(n),q(n);for(int i=0;i<n;i++)cin>>p[i]>>q[i];//正常读入x和yauto x=solve(p),y=solve(q);ll ans=0;for(int i=0,j=y.size()-1;i<x.size();i++){while(x[i]+y[j]>d&&j>=0)j--;ans=ans+j+1;}cout<<ans<<endl;
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);ll T=1;
// cin>>T;while(T--){Jiuyuan();}return 0;
}
