[洛谷]P2313 [HNOI2005] 汤姆的游戏（模拟）

1：思路：一看N<=500,再看一下题目，嗯.....，模拟！，直接暴力为每个点都遍历一些所有图形，如果在里面就个数就加一。

2：复杂度：O（N*M）

3：一个小小的坑（俺不小心踩了，不~）：

当某点在一个图形的边界上时，我们认为该点不在这个图形的内部

4：ACcode:

 
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e2+10;
struct E {
	double x1,y1,x2,y2,r;
	char c;
} e[N];
int n,m;
void solve() {
	cin>>n>>m;
	for(int i=1; i<=n; i++) {
		cin>>e[i].c;
		if(e[i].c=='r') {
			cin>>e[i].x1>>e[i].y1>>e[i].x2>>e[i].y2;
		} else {
			cin>>e[i].x1>>e[i].y1>>e[i].r;
		}
	}
	while(m--) {
		double x,y;
		cin>>x>>y;
		int cnt=0;
		for(int i=1; i<=n; i++) {
			if(e[i].c=='r') {
				if(x>e[i].x1&&x<e[i].x2&&y>e[i].y1&&y<e[i].y2) {
					cnt++;
				}
			} else {
				if(sqrt((x-e[i].x1)*(x-e[i].x1)+(y-e[i].y1)*(y-e[i].y1))<e[i].r) {
					cnt++;
				}
			}
		}
		cout<<cnt<<"\n";
	}
 
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int t=1;
	//cin>>t;
	while(t--) {
		solve();
	}
	return 0;
}
 
 
 

over~