学步园

题目链接

典型的二分搜索的模板题。

先排序在搜索，数据量好大~~ 用o（n）的暴力求法 一定超时

这里还用到了  文氏图中 的一些知识

即 所有人 - 圆圈1中的人 - 圆圈2中的人就是答案；

先求出距离，对距离排序，再二分就好了。

也可以看队长的blog

下面是我这道题的二分搜索的代码。

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;
const int maxn=210000;
int n;
struct node{
     int x,y;		
}point[maxn],circle[2];

int r1[maxn],r2[maxn];
int cal(node a,node b){     //计算距离 题意中都是整数，直接平方就好了
	return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
int find(int num,int *p){   //关键步骤 二分
	int left=0,right=n+1;
	p[n+1]=1000000000;
	while(right-left>1){
	   int middle=(left+right)/2;      
	   if( p[middle]>num ) right=middle;   //的出来的数据 a[left]<=num; a[right]>num;由（1）（2）代码  可得结果
	   else left=middle;                   //(2)
	}	
	return left;
}



int main()
{
    int cas=1;
	while(scanf("%d",&n)!=EOF){
        if(n==0)break;
		printf("Case %d:\n",cas++);        
		for(int i=1;i<=n;i++)
		   scanf("%d %d",&point[i].x,&point[i].y);
		scanf("%d%d%d%d",&circle[0].x,&circle[0].y,&circle[1].x,&circle[1].y);
	    for(int i=1;i<=n;i++){
               r1[i]=cal(point[i],circle[0]);
	       r2[i]=cal(point[i],circle[1]);
        }
	    sort(r1+1,r1+1+n);
	    sort(r2+1,r2+1+n);        //排序和求距离要放到query的上面。要不查询次数太多会超时
		int query;
		scanf("%d",&query);
		while(query--){
		     int len1,len2;
			 scanf("%d%d",&len1,&len2);
			 len1=len1*len1;
			 len2=len2*len2;
			 int ans1=find(len1,r1);
			 int ans2=find(len2,r2);
			 printf("%d\n",max(n-ans1-ans2,0));  //文氏图的求解 集合的运算
	    }
	}
    return 0;		
}