油漆面积（2017年蓝桥杯）

时间限制 2s 内存限制 256M

       问题描述：X星球的一批考古机器人正在一片废墟上考古。该区域的地面坚硬如石、平整如镜。管理人员为了方便，建立了标准的直角坐标系。每个机器人都各有特长、身怀绝技。它们感兴趣的内容也不相同。经过各种测量，每个机器人都会报告一个或多个矩形区域作为优先考古的区域。矩形的表示格式为(x1,y1,y1,y2)[其中1，2为下标]，代表矩形的两个对角点的坐标。为了醒目，总部要求对所有机器人选中的矩形涂黄色油漆。小明并不需要当油漆工，只是他需要计算一下一共要耗费多少油漆。其实这也不难，只要计算出所有矩形覆盖的区域一共有多大面积就可以了。注意，各个矩形之间可能重叠。

     本题的输入为若干矩形，要求输出其覆盖的总面积。

    输入：输入的第一行包含一个整数n，表示有多少个矩形，n >= 1 && n < 10000。接下来的n行，每行有4个整数x1、y1、x2、y2(数字 1，2为下标)，以空格分隔，表示矩形的两个对角点的坐标。 x1,y1,x2,y2(1,2为下标) >=0 && <= 10000。

    输出：输出一个整数，表示矩形覆盖的总面积。

【输入样例】

3

1   5   10   10

3   1    20   20

2   7    15    17 

【输出样例】

340

【题目解析】

       本题的题意非常简单，输入若干矩形，求它们覆盖的总面积是多少。这道题是一道中等难度题。题目难的原因是矩形数量n和顶点坐标值都很大。这道题的数学模型是“矩形面积并”，解题方案是“扫描线”，编码的正解需要用到线段树，能在紧张的赛场上做出来很难。

      如果本题用简单方法做，在n和坐标值较小的情况下可以通过30%左右的测试。

      大家容易想到一种简单方法。把平面划分成单位边长为1（面积也是1）的方格。每读入一个矩形，就把它覆盖的单位方格标注为已覆盖。对所有输入的矩形都是这样处理，统计出所有被覆盖的方格的数量，就是总面积。

    这个简单方法不需要处理矩形之间的关系，编码很简单。用vis[x][y]表示坐标(x,y)所在的方格是否被覆盖。依次读入n个矩形，累加被覆盖的方格的数量，就是答案。

【参考程序如下】

#include <iostream>
using namespace std;
bool vis[10001][10001];       //100M内存 
int main(int argc, char** argv) {
	int n,sum = 0;     // sum 总面积
	cin >> n;
	for(int k = 0;k < n;k++)
	{
		int x1,y1,x2,y2;
		cin >> x1 >> y1 >> x2 >> y2;          //读一个矩形
		if(x1 > x2) swap(x1,x2);     //坐标排序
		if(y1 > y2) swap(y1,y2);      
	  for(int i = x1; i < x2; i++)    // 检查这个矩形覆盖的方格
	      for(int j = y1; j < y2; j++) 
		  if(!vis[i][j])    // 这个方格没有被覆盖过，需要累加面积 
		  {
		  	sum++;
		  	vis[i][j] = 1;      // 标注为已经覆盖，后面不再累加 
		   } 
	 } 
	    cout << sum;
	return 0;
}

【程序运行结果如下】