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 }