C++分析研究  
C++
日历
<2013年9月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
293012345
统计
  • 随笔 - 92
  • 文章 - 4
  • 评论 - 4
  • 引用 - 0

导航

常用链接

留言簿

随笔档案

文章档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜

 

 给定n个点的坐标
圆1的坐标 圆2的坐标 询问次数
圆1的半径 圆2的半径
问:对于每个询问,求出(不在圆上的点 - 在2圆重合 部分的点 ) //注意当答案<0 输出0托福答案
思路:首先对题意转化,可以看成是求 n - (在圆1上的点)-(在圆2上的点)
因为所有点是固定的,所以 (在圆1的点) => DIS( 点,圆心1) <= R1
只要求出所有满足上述不等式点的个数即可
把所有点按 (到圆心1的距离)小到大排序,存在p1数组中,再把p1中有相同dis的点去重后存在k1数组中,k1.num 就表示 距离<=k1.dis的点有 k1.num个托福改分
然后二分找到k1.dis <= R1 的最大的k1.num ,就是(在圆1上的点)
对圆2上的点相同操作
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define inf 2000000
#define N 200200
using namespace std;
struct node{
int x,y;
int dis;
bool operator<(const node& a)const {return a.dis>dis;}
}p1[N],p2[N],r1,r2;
struct kk{
int dis,num;
}k1[N],k2[N];
int kn1,kn2;
int R1,R2,sum1,sum2,n;
int DIS(node a,node b){return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}
int erfen1(int l,int r,int d){
if(l==r-1 && k1[l].dis<=d && k1[r].dis>d )
return k1[l].num;
int mid=(l+r)》1;
if(k1[mid].dis>d)return erfen1(l,mid,d);
if(k1[mid].dis
if(k1[mid].dis==d)return k1[mid].num;
}
int erfen2(int l,int r,int d){
if(l==r-1 && k2[l].dis<=d && k2[r].dis>d )
return k2[l].num;
int mid=(l+r)》1;
if(k2[mid].dis>d)return erfen2(l,mid,d);
if(k2[mid].dis
if(k2[mid].dis==d)return k2[mid].num;
}
void quchong(){//p数组去重得到k数组
int i;
for(i=1;i<=n;i++)
{
if(p1[i].dis==p1[i-1].dis)k1[kn1].num++;
else
{
kn1++;
k1[kn1].dis=p1[i].dis;
k1[kn1].num=1+k1[kn1-1].num;
}
if(p2[i].dis==p2[i-1].dis)k2[kn2].num++;
else
{
kn2++;
k2[kn2].dis=p2[i].dis;
k2[kn2].num=1+k2[kn2-1].num;
}
}
}
int main(){
int i,j,query,Cas=1;
p1[0].dis=p2[0].dis=-1; //去重边界
while(scanf("%d",&n),n){
for(i=1;i<=n;i++)scanf("%d%d",&p1[i].x,&p1[i].y),p2[i]=p1[i];
scanf("%d %d %d %d %d",&r1.x,&r1.y,&r2.x,&r2.y,&query);
for(i=1;i<=n;i++)
p1[i].dis=DIS(p1[i],r1), p2[i].dis=DIS(p2[i],r2);
sort(p1+1,p1+n+1);
sort(p2+1,p2+n+1);
kn1=kn2=0;
quchong();
k1[0].dis=k2[0].dis=-1; //二分需要的边界条件
k1[0].num=k2[0].num=0;

k1[kn1+1].dis=k2[kn2+1].dis=inf; //二分需要的边界条件
printf("Case %d:\n",Cas++);
while(query--)
{
scanf("%d %d",&R1,&R2);
sum1=erfen1(1,kn1,R1*R1);
sum2=erfen2(1,kn2,R2*R2);
int ans=n-sum1-sum2;
if(ans<0)ans=0;
printf("%d\n",ans);
}
}
return 0;
}
/*
11
95 75
27 6
93 5
124 13
34 49
65 61
81 49
77 33
110 50
91 22
110 25
57 42 97 36 2
31 25
25 25
15
1 1
2 2
3 3
4 4
5 5
10 5
15 5
1 0
2 0
3 0
4 0
5 0
6 0
10 0
20000 20000
10 0 5 5 2
7 1
8 1
ans:
2
2
8
3
*/

posted on 2013-09-08 09:59 HAOSOLA 阅读(167) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


 
Copyright © HAOSOLA Powered by: 博客园 模板提供:沪江博客
PK10开奖 PK10开奖