简单解题思路

问题描述

给定一个 矩形区域（长 x，宽 y）和若干个 圆形障碍物（每个圆形由中心坐标 (tx, ty) 和半径 r 描述），要求计算 未被圆形障碍物覆盖的区域面积。

核心思路

1. 圆形转矩形：

   • 将每个圆形障碍物转换为一个 外接正方形（边长为 2r，坐标范围 [tx-r, ty-r] 到 [tx+r, ty+r]）。

2. 矩形合并：

   • 检查所有矩形是否有重叠或相交。
   • 如果两个矩形相交，则合并成一个更大的矩形（取最小 sx, sy 和最大 ex, ey）。
   • 重复合并过程，直到没有可合并的矩形。

3. 计算剩余面积：

   • 初始总面积 = x * y。
   • 减去所有未被合并的矩形的面积，得到未被覆盖的区域面积。

关键步骤

1. 输入处理：

   • 读取矩形区域大小 x, y 和圆形障碍物数量 n。
   • 对每个圆形障碍物，生成对应的外接正方形并存储。

2. 矩形合并：

   • 使用双重循环检查每对矩形是否相交（inter() 方法）。
   • 如果相交，合并两个矩形（merge() 方法），并标记其中一个为已合并（vis = true）。
   • 重复该过程，直到没有可合并的矩形。

3. 计算最终面积：

   • 遍历所有未被合并的矩形（vis = false），减去它们的面积。
   • 输出剩余面积。

总结

• 核心算法：矩形相交判断 + 贪心合并。
• 适用场景：计算障碍物覆盖区域、碰撞检测、几何图形处理等。
• 优化点：合并过程可以优化（如使用并查集），但本题数据规模较小，暴力合并可行。

#include <cstdio>
#include <algorithm>
using namespace std;
#define N 105
int x, y, n, tx, ty, r, ans;
struct Rec
{
	int sx, sy, ex, ey;
	bool vis;
	Rec() {}
	Rec(int _sx, int _sy, int _ex, int _ey, bool f): sx(_sx), sy(_sy), ex(_ex), ey(_ey), vis(f) {}
	bool contains(int x, int y)
	{
		return (x<=ex && x>=sx && y<=ey && y>=sy);
	}
	bool inter(Rec &r)
	{
		if (contains(r.sx, r.sy)) return true;
		if (contains(r.sx, r.ey)) return true;
		if (contains(r.ex, r.sy)) return true;
		if (contains(r.ex, r.ey)) return true;
		if (r.contains(sx, sy)) return true;
		if (r.contains(sx, ey)) return true;
		if (r.contains(ex, sy)) return true;
		if (r.contains(ex, ey)) return true;
		return false;
	}
	void merge(Rec &r)
	{
		sx = min(sx, r.sx);
		sy = min(sy, r.sy);
		ex = max(ex, r.ex);
		ey = max(ey, r.ey);
	}
	int area()
	{
		return (ey-sy) * (ex-sx);
	}
	void print()
	{
		printf("%d %d %d %d %d\n", sx, sy, ex, ey, vis);
	}
};
Rec rec[N];
int main()
{
	scanf("%d%d%d", &x, &y, &n);
	ans = x*y;
	for (int i = 0; i < n; ++ i)
	{
		scanf("%d%d%d", &tx, &ty, &r);
		rec[i] = Rec(tx-r, ty-r, tx+r, ty+r, false);
	}
	bool flag;
	while (true)
	{
		flag = false;
		for (int i = 0; i < n; ++ i) if (!rec[i].vis)
		{
			for (int j = 0; j < n; ++ j) if (j!=i && !rec[j].vis && rec[i].inter(rec[j]))
			{
				flag = true;
				rec[j].vis = true;
				rec[i].merge(rec[j]);
			}
		}
		if (!flag) break;
	}
	for (int i = 0; i < n; ++ i) if (!rec[i].vis)
		ans -= rec[i].area();
	printf("%d\n", ans);
}