洛谷 P2313 [HNOI2005]汤姆的游戏(计算几何)

Description:

汤姆是个好动的孩子,今天他突然对圆规和直尺来了兴趣。于是他开始在一张很大很大的白纸上画很多很多的矩形和圆。画着画着,一不小心将他的爆米花弄撒了,于是白纸上就多了好多好多的爆米花。汤姆发现爆米花在白纸上看起来就像一个个点,有些点落在矩形或圆内部,而有些则在外面。于是汤姆开始数每个点在多少个矩形或圆内部。毕竟汤姆还只是个孩子,而且点、矩形和圆又非常多。所以汤姆数了好一会都数不清,于是就向聪明的你求助了。你的任务是：在给定平面上N个图形(矩形或圆)以及M个点后，请你求出每个点在多少个矩形或圆内部(这里假设矩形的边都平行于坐标轴)。

Input:

从文件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:

输出文件output.txt中包含M行,每行是一个整数,其中第i行的整数表示第i个点在多少个图形内部(当某点在一个图形的边界上时，我们认为该点不在这个图形的内部)。

Sample Input:

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

Sample Output:

1
2
0
1

题目链接

5e2的数据范围可以直接枚举点暴力判断是否在图形内。

AC代码:

#include <bits/stdc++.h>
using namespace std;

const int maxn = 5e2 + 5;

struct Point {
	double X, Y;
	void Input() {
		scanf("%lf%lf", &X, &Y);
	}
};

struct Rectangle {
	double X1, Y1, X2, Y2;
	void Input() {
		double TempX1, TempY1, TempX2, TempY2;
		scanf("%lf%lf%lf%lf", &TempX1, &TempY1, &TempX2, &TempY2);
		X1 = min(TempX1, TempX2);
		Y1 = max(TempY1, TempY2);
		X2 = max(TempX1, TempX2);
		Y2 = min(TempY1, TempY2);
	}
	bool Judge(Point P) {
		return P.X > X1 && P.X < X2 && P.Y > Y2 && P.Y < Y1;
	}
};

struct Circle {
	double X, Y, R;
	void Input() {
		scanf("%lf%lf%lf", &X, &Y, &R);
	}
	bool Judge(Point P) {
		return hypot(fabs(P.X - X), fabs(P.Y - Y)) < R;
	}
};

int N, M;
Rectangle rectangles[maxn];
Circle circles[maxn];
int RCnt, CCnt;
Point points[maxn];
int Answer[maxn];

int main(int argc, char *argv[]) {
	scanf("%d%d", &N, &M);
	RCnt = 0, CCnt = 0;
	for (int i = 0; i < N; ++i) {
		char Graph;
		cin >> Graph;
		if (Graph == 'r') {
			rectangles[RCnt++].Input();
		}
		else {
			circles[CCnt++].Input();
		}
	}
	for (int i = 0; i < M; ++i) {
		points[i].Input();
	}
	memset(Answer, 0, sizeof(Answer));
	for (int i = 0; i < RCnt; ++i) {
		for (int j = 0; j < M; ++j) {
			if (rectangles[i].Judge(points[j])) {
				Answer[j]++;
			}
		}
	}
	for (int i = 0; i < CCnt; ++i) {
		for (int j = 0; j < M; ++j) {
			if (circles[i].Judge(points[j])) {
				Answer[j]++;
			}
		}
	}
	for (int i = 0; i < M; ++i) {
		printf("%d\n", Answer[i]);
	}
    return 0;
}