P2313 [HNOI2005]汤姆的游戏
题目描述
汤姆是个好动的孩子,今天他突然对圆规和直尺来了兴趣。于是他开始在一张很大很大的白纸上画很多很多的矩形和圆。画着画着,一不小心将他的爆米花弄撒了,于是白纸上就多了好多好多的爆米花。汤姆发现爆米花在白纸上看起来就像一个个点,有些点落在矩形或圆内部,而有些则在外面。于是汤姆开始数每个点在多少个矩形或圆内部。毕竟汤姆还只是个孩子,而且点、矩形和圆又非常多。所以汤姆数了好一会都数不清,于是就向聪明的你求助了。你的任务是:在给定平面上N个图形(矩形或圆)以及M个点后,请你求出每个点在多少个矩形或圆内部(这里假设矩形的边都平行于坐标轴)。
输入格式
从文件input.txt中读入数据,文件第一行为两个正整数N和M,其中N表示有多少个图形(矩形或圆),M表示有多少个点。接下来的N行是对每个图形的描述,具体来说,第i+1行表示第i个图形。先是一个字母,若该字母为“r”,则表示该图形是一个矩形,这时后面将有4个实数x1,y1,x2,y2,表示该矩形的一对对角顶点的坐标分别为(x1,y1)和(x2,y2);若该字母为“c”,则表示该图形是一个圆,这时后面将有3个实数x,y,r,表示该圆以(x,y)为圆心并以r为半径。最后M行是对每个点的描述,其中每行将有两个实数x,y,表示一个坐标为(x,y)的点。
思路
取两个数组分别存放矩形的坐标和圆的圆心坐标和半径长度,再取一个数组存放点的坐标,最后取一个数组判断对应点的情况,注意不包括边界。
代码
1 #include <stdio.h> 2 #include <math.h> 3 double ju[500][4]; 4 double yuan[500][3]; 5 double dian[500][2]; 6 int main(){ 7 char c; 8 int n,m; 9 int i=0,j=0,k; 10 int a=0,b=0; 11 int p[500]={0}; 12 scanf("%d %d\n",&n,&m); 13 for(i=0;i<n;i++){ 14 scanf("%c ",&c); //判断图形是矩形还是圆形 15 if(c=='r'){ 16 scanf("%lf %lf %lf %lf\n",&ju[a][0],&ju[a][1],&ju[a][2],&ju[a][3]); //注意要有换行符 17 a++; //计算矩形的个数 18 } 19 if(c=='c'){ 20 scanf("%lf %lf %lf\n",&yuan[b][0],&yuan[b][1],&yuan[b][2]); 21 b++; //计算圆形的个数 22 } 23 } 24 for(i=0;i<m;i++){ 25 scanf("%lf %lf",&dian[i][0],&dian[i][1]); 26 } 27 for(i=0;i<m;i++){ 28 for(j=0;j<a;j++){ 29 if(dian[i][0]>ju[j][0]&&dian[i][0]<ju[j][2]&&dian[i][1]>ju[j][1]&&dian[i][1]<ju[j][3]) //判断是否在矩形内 30 p[i]++; 31 } 32 for(k=0;k<b;k++){ 33 if(sqrt((yuan[k][0]-dian[i][0])*(yuan[k][0]-dian[i][0])+(yuan[k][1]-dian[i][1])*(yuan[k][1]-dian[i][1]))<yuan[k][2]) //判断是否在圆内 34 p[i]++; 35 } 36 } 37 for(i=0;i<m;i++){ 38 printf("%d\n",p[i]); 39 } 40 return 0; 41 }
标签:汤姆,每日,int,坐标,图形,矩形,500 From: https://www.cnblogs.com/Amon01/p/17053689.html