题目链接：
http://acdream.info/problem?pid=1127
题目：
移动通信系统中，通信网的建立主要通过基站来完成。
基站可以分为主基站和子基站。子基站和各个移动用户进行连接，子基站必须通过主基站来和外界实现通信。主基站可以覆盖到的范围是一个圆形区域，子基站和主基站的距离小于半径r才能被该主基站覆盖到。半径r由主基站的发射功率确定。
某个区域的移动通信网，包含2个主基站和N个子基站。它们的位置都可以对应到一个整数坐标上。如果子基站至少被一个主基站覆盖，则该子基站是激活的。
现在通信公司在调试设备，它们不停地改变主基站的发射功率，当两个主基站的覆盖半径分别为r1和r2时，需要知道有多少个子基站处于非激活状态。
题解：
对坐标进行转化，子基站对到主基站1(x1,y1)的距离转化为X轴，子基站对到主基站2(x2,y2)的距离转化为Y轴。然后对( 子基站到主基站2(x2,y2)的距离和主基站2的覆盖半径) 进行离散化处理。
然后按X轴进行降序排序，最后将Y轴插入到树状数组中进行维护和离线查询就行了。
复杂度：\(O(m*logn)\)
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+100;
const int mod = 1e9+7;
struct node
{
int x,y;
int id;
bool operator < (const node &a) {
return (x == a.x && id < a.id) || (x > a.x);
}
}node[maxn];
int num[maxn];
int ans[maxn];
map<int,int>mp;
int sum[maxn];
int k;
void update(int pos,int val){
// std::cout << "k=" << k << '\n';
while(pos<=k)
{
sum[pos]+=val;
pos += (pos&-pos);
}
}
int query(int pos) {
int res = 0;
while(pos)
{
res += sum[pos];
pos -= (pos&-pos);
}
return res;
}
double distance(double x1,double y1,double x2,double y2)
{
return (double)sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int main(int argc, char const *argv[]) {
int x1,x2,y1,y2;
int n,m,x,y;
while(std::cin >> x1 >> y1 >> x2 >> y2)
{
mp.clear();
k = 0;
std::cin >> n;
for(int i=1;i<=n;i++) {
std::cin >> x >> y;
node[i].x = (int)distance(x,y,x1,y1);
node[i].y = (int)distance(x,y,x2,y2);
node[i].id = -i;
num[k++] = node[i].y;
}
std::cin >> m;
for(int i=1;i<=m;i++) {
std::cin >> node[i+n].x >> node[i+n].y;
node[i+n].id = i;
num[k++] = node[i+n].y;
}
sort(num,num+k);
k = unique(num,num+k)-num;
for(int i=0;i<k;i++) {
mp[num[i]] = i+1;
}
sort(node+1,node+n+m+1);
memset(sum,0,sizeof( sum ));
for(int i=1;i<=n+m;i++) {
int pos = mp[node[i].y];
// std::cout << "now= " <<node[i].x<<" "<< node[i].y <<" " << node[i].id<<" " << pos << '\n';
if(node[i].id < 0) {
update(pos,1);
}
else if(node[i].id >= 1){
ans[node[i].id] = query(k) - query(pos-1);
}
}
for(int i=1;i<=m;i++) {
std::cout << ans[i] << '\n';
}
}
// cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
return 0;
}
转载于:https://www.cnblogs.com/LzyRapx/p/8378082.html
