3960415_wa.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>

using namespace std;

struct circle
{
	int lx, rx, uy, dy;
	int x, y, r;

	bool operator < (const circle c)	const
	{
		return this->r < c.r;
	}

	circle(int x, int y, int r)
	{
		this->x = x;
		this->y = y;
		this->r = r;
	}

	circle() {}

}c[100];

int max(int a, int b)
{
	return a < b ? b : a;
}

int min(int a, int b)
{
	return a < b ? a : b;
}

int main()
{
	int x, y, r;
	int w, h, n;
	int i, j;

	scanf("%d%d%d", &w, &h, &n);
	for (i = 0; i < n; i++)
	{
		scanf("%d%d%d", &x, &y, &r);
		c[i] = circle(x, y, r);
		c[i].lx = c[i].x - c[i].r;c[i].rx = c[i].x + c[i].r;
		c[i].uy = c[i].y + c[i].r;c[i].dy = c[i].y - c[i].r;
	}
	sort(c, c + n);
	int mark[100];
	memset(mark, 0, sizeof(mark));
	int ans = w * h;
loop:
	bool flag = false;
	for (i = 0; i < n; i++)
	{
		if (mark[i] == 1)
		{
			continue;
		}
		int lx, rx, uy, dy;
		int xl, xr, yu, yd;
		lx = c[i].lx;rx = c[i].rx;
		uy = c[i].uy;dy = c[i].dy;
		for (j = i + 1; j < n; j++)
		{
			if (mark[j] == 1)
			{
				continue;
			}
			xl = c[j].lx;xr = c[j].rx;
			yd = c[j].dy;yu = c[j].uy;
			if (xl == lx && xr == rx && yu == uy && yd == dy)
			{
				flag = true;
				mark[j] = 1;
				continue;
			}
			if ((lx <= xl && xl <= rx && dy <= yd && yd <= uy) ||
				(lx <= xr && xr <= rx && dy <= yd && yd <= uy) ||
				(lx <= xl && xl <= rx && dy <= yu && yu <= uy) ||
				(lx <= xr && xr <= rx && dy <= yu && yu <= uy) )
			{
				mark[j] = 1;
				flag = true;
				lx = min(lx, xl);rx = max(rx, xr);
				uy = max(uy, yu);dy = min(dy, yd);
				c[i].lx = lx;c[i].rx = rx;
				c[i].uy = uy;c[i].dy = dy;
			}
		}
	}
	if (flag == true)
	{
		goto loop;
	}
	for (i = 0; i < n; i++)
	{
		if (mark[i] == 0)
		{
			ans -= (c[i].rx - c[i].lx) * (c[i].uy - c[i].dy);
		}
	}
	printf("%d\n", ans);
	return 0;
}