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)的点。
输出格式
输出文件output.txt中包含M行,每行是一个整数,其中第i行的整数表示第i个点在多少个图形内部(当某点在一个图形的边界上时，我们认为该点不在这个图形的内部)。
输入输出样例
输入 #1
3 4
r 1.015 0.750 5.000 4.000
c 6.000 5.000 2.020
r 6.500 7.200 7.800 9.200
3.500 2.500
4.995 3.990
2.300 8.150
6.900 8.000
输出 #1
1
2
0
1
说明/提示
对于100%的数据，(N,Mle 500)
【思路】
数学基础 + 枚举
求一个点在多少个图形的里面
很暴力的一道题目，
看n和m的范围只有500
所以完全可以枚举每一个点
再去和每一个图形的范围去比较
如果在范围内
那就计数器累加
如果不咋那就跳过去
直到枚举完成每一个图形
这个时候输出计数器
那么这个点的任务就完成了
上面就是总体的思路
再来说一下细枝末节
输入的时候怎么搞呢？
用一个结构体储存！
但是这有两种情况啊？！难道要开两个结构体！
完全不需要的，你开一个结构体
里面放着一个存字符的acioi和整形的x1,x2,y1,y2
这样如果acioi是r那整形的四个变量都要用到
储存两个对角顶点的坐标
如果acioi是c那就只用到里面的三个
x1是圆心的x坐标，y1是圆心的y坐标
x2则是圆的半径
注意：我这样处理仅仅是个人喜好！看起来方便！也没有多么考虑空间哪一个更优一些
然后再说一下判断是否在某一个图形里面
如果是矩形的话
那只要你这个点的x和y同时满足x>x1，y>y1,,x<x2,y<y2或者同时满足x<x1,y<y1,x>x2,y>y2
也就是这个点的坐标在其中一个点的左下方，在另一个点的左上方
如果是圆的话
那这个就很好处理了，因为圆在每个方向上的长度都是一样的
都是半径r（结构体中即为x2）
用两点之间距离公式求出这个点到圆心的距离
然后和半径比较
如果比半径小那就是在这个点的范围内
反之则不在
注意：要开double或者float类型!
提示：两点之间距离等于 (sqrt{(x1-x2)^2 + (y1 - y2) ^ 2})
【完整代码】
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int Max = 505;
struct node
{
char acioi;
double x1,y1;
double x2,y2;
}a[Max];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;++ i)
{
cin >> a[i].acioi;
if(a[i].acioi == 'r')
cin >> a[i].x1 >> a[i].y1 >> a[i].x2 >> a[i].y2;
else
cin >> a[i].x1 >> a[i].y1 >> a[i].x2;
}
double x,y;
for(int i = 1;i <= m;++ i)
{
cin >> x >> y;
int js = 0;
for(int j = 1;j <= n;++ j)
{
if(a[j].acioi == 'r')
{
if((a[j].x1 > x && a[j].y1 > y && a[j].x2 < x && a[j].y2 < y) || (a[j].x1 < x && a[j].y1 < y && a[j].x2 > x && a[j].y2 > y) )
js ++;
}
else
{
if( sqrt((a[j].x1 - x) * (a[j].x1 - x) + (a[j].y1 - y) * (a[j].y1 - y)) < a[j].x2)
js ++;
}
}
cout << js << endl;
}
return 0;
}