Leetcode 391. Perfect Rectangle

 

正确的答案应当满足：

1.最大的长方形面积等于所有长方形的面积之和

2.除了四个顶点出现的次数为1，其他点出现次数必须为2/4次

class Solution {
public:
	bool isRectangleCover(vector<vector<int>>& rectangles) {
		//记录四边形顶点出现次数
		unordered_map<string, int> vertex_count;
		//记录总面积
		int area = 0;

		for (auto rect : rectangles) {
			area += (rect[3] - rect[1]) * (rect[2] - rect[0]);
			vector<string> vertex = { to_string(rect[0]) + '_' + to_string(rect[1]),
							   to_string(rect[2]) + '_' + to_string(rect[3]),
							   to_string(rect[0]) + '_' + to_string(rect[3]),
							   to_string(rect[2]) + '_' + to_string(rect[1]) };
			for (auto v : vertex)
				vertex_count[v]++;
		}
		// 四个顶点（出现一次）
		vector<vector<int>> four_vertex;
		for (auto iterator = vertex_count.begin(); iterator != vertex_count.end(); ++iterator) {
			if (iterator->second == 1) {
				int index = iterator->first.find('_');
				four_vertex.push_back({ stoi(iterator->first.substr(0, index)), stoi(iterator->first.substr(index + 1)) });
			}

			//其他顶点出现2次或4次
			else if (iterator->second != 2 && iterator->second != 4) {
				return false;
			}
		}
		if (four_vertex.size() != 4) {
			return false;
		}
		int height = max(abs(four_vertex[0][1] - four_vertex[1][1]), abs(four_vertex[0][1] - four_vertex[2][1]));
		int weight = max(abs(four_vertex[0][0] - four_vertex[1][0]), abs(four_vertex[0][0] - four_vertex[2][0]));
		//所有长方形面积之和 = 通过四个顶点计算的总面积
		if (height * weight != area) {
			return false;
		}

		return true;
	}
};